Constructing Small Sample Spaces for De � Randomization of Algorithms
The subject of this paper is nding small sample spaces for joint distributions of n Bernoulli random variables where the probabilities of some events are prescribed The problem of recognizing whether the prescribed probabilities are consistent is NP hard It is shown however that if the probabilities are consistent then there exists a sample space that supports them whose cardinality does not exceed the number of events with prescribed probabilities It is also shown that if the probabilities are consistent with a joint distribution of n independent Bernoulli variables then a small sample space can be constructed in polynomial time This last result is useful for converting randomized algorithms into deterministic ones We demonstrate this technique by an application to the problem of nding large independent sets in sparse hypergraphs