| Abstract (De) r andomized Construction of Small Sample Spaces in NC (2009) | |||||||||||||||
Abstract | |||||||||||||||
| Koller and Megiddo introduced the paradigm of con-structing compact distributions that satisfy a given set of constraints, and showed how it can be used to efi-ciently 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) algo-rithm for constructing a compact distribution that sat-isfies 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 inde-pendence constraints as well as constraints over events relating to the parity OT sum of a certain set of vari-ables. OUT construction relies on a new and indepen-dently interesting parallel algorithm for converting a solution to a linear system into an almost basic ap-proximate solution to the same system. We use these techniques in the first AfC derandomization of an al-gorithm for constructing large independent sets in d-uniform hypergraphs for arbitrary d. We also show how the linear programming perspective suggests new proof techniques which might be useful in general prob-abilistic analysis. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||