(De)randomized Construction of Small Sample Spaces in NC

摘要

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 efficiently derandomize certain types of algorithms. In this paper, we significantly extend their results in two ways. First, we show how their approach can be applied to deal with more generalexpectation constraints. More importantly, we provide the firstparallel(NC) algorithm for constructing a compact distribution that satisfies the constraints up to a smallrelativeerror. This algorithm deals with constraints over any event that can be verified by finite automata, including allindependence constraintsas well as constraints over events relating to the parity or sum of a certain set of variables. Our 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 NC derandomization of an algorithm for constructing large independent sets ind-uniform hypergraphs forarbitrary d. We also show how the linear programming perspective suggests new proof techniques which might be useful in general probabilistic analysis.