Title

The Fourth Moment In Luby'S Distribution

Keywords

Derandomization; Fourth moment; Full independence; k-wise independence

Abstract

Luby (1988) proposed a way to derandomize randomized computations which is based on the construction of a small probability space whose elements are 3-wise independent. In this paper we prove some new properties of Luby's space. More precisely, we analyze the fourth moment and prove an interesting technical property which helps to understand better Luby's distribution. As an application, we study the behavior of random edge cuts in a weighted graph. © 1995.

Publication Date

8-21-1995

Publication Title

Theoretical Computer Science

Volume

148

Issue

1

Number of Pages

133-140

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0304-3975(95)00056-3

Socpus ID

58149363865 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/58149363865

This document is currently not available here.

Share

COinS