Title

The 4Th Moment In Luby Distribution

Authors

Authors

D. P. Dubhashi; G. E. Pantziou; P. G. Spirakis;C. D. Zaroliagis

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Theor. Comput. Sci.

Keywords

FOURTH MOMENT; FULL INDEPENDENCE; K-WISE INDEPENDENCE; DERANDOMIZATION; INDEPENDENT SET PROBLEM; PARALLEL ALGORITHM; Computer Science, Theory & Methods

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.

Journal Title

Theoretical Computer Science

Volume

148

Issue/Number

1

Publication Date

1-1-1995

Document Type

Note

DOI Link

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

Language

English

First Page

133

Last Page

140

WOS Identifier

WOS:A1995RP82600009

ISSN

0304-3975

Recommended Citation

"The 4Th Moment In Luby Distribution" (1995). Faculty Bibliography 1990s. 1327.
https://stars.library.ucf.edu/facultybib1990/1327