The 4Th Moment In Luby Distribution

    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

    Language

    English

    First Page

    133

    Last Page

    140

    WOS Identifier

    WOS:A1995RP82600009

    ISSN

    0304-3975

    Share

    COinS