(De)randomized construction of small sample spaces in NC (1997)by D.R. Karger and D. Koller [older version, 1994]
Abstract:
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 algorithm. In this paper, we significantly extend their results 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\/ (NC) 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 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 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.
Download Information
D.R. Karger and D. Koller (1997). "(De)randomized construction of small sample spaces in NC." Journal of Computer and System Sciences, 55(3), 402413.
Full version of paper from FOCS '94.


Bibtex citation
@article{Karger+Koller:97,
author = {D.R. Karger and D. Koller},
title = {(De)randomized construction of small sample spaces in NC},
journal = {Journal of Computer and System Sciences},
volume = 55,
number = 3,
month = {December},
year = 1997,
pages = {402413},
note = {Full version of paper from FOCS '94},
}
full list
