language-icon Old Web
English
Sign In

De) r andomized Construction

1994 
Koller and Megiddo introduced the paradigm of constructing compact distributions that satisfy a given set of constraints, and showed how it can be used to e ficiently derandomize certain types of algorithm. In this paper, we significantly extend their resdts in two ways. First, we show how their approach can be applied to deal with more general expectation constraints. More importantly, we provide the first parallel (Ne) algorithm for constructing a compact distribution that satisfies the constraints up to a small relative error. This algorithm deals with constraints over any event that can be verified by finite automata, including all independence constraints as well as constraints over events relating to the parity OT sum of a certain set of variables. OUT construction relies on a new and independently interesting parallel algorithm for converting a solution to a linear system into an almost basic approximate solution to the same system. We use these techniques in the first AfC derandomization of an algorithm for constructing large independent sets in duniform hypergraphs for arbitrary d. We also show how the linear programming perspective suggests new proof techniques which might be useful in general probabilistic analysis.
    • Correction
    • Cite
    • Save
    • Machine Reading By IdeaReader
    17
    References
    0
    Citations
    NaN
    KQI
    []