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 d<\I>-uniform
hypergraphs for arbitrary d. We also show how the linear
programming perspective suggests new proof techniques which might be
useful in general probabilistic analysis.