Sample spaces uniform on neighborhoods

摘要

Let a universe of m elements be given, along with a family of subsets of the universe (neighborhoods), each of size at most k. We describe methods for assigning the m elements to points in a small-dimensional vector space (over GF(2)), in such a way that the elements in each neighborhood are assigned to an independent set of vectors.

Such constructions lead, through a standard correspondence between linear and statistical independence, to the construction of small sample spaces which restrict to the uniform distribution in each neighborhood. (The sample space is a uniformly-weighted family of binary m-vectors).

The size of such a small space will be a function of the number of neighborhoods; and for sparse families, will be substantially smaller than any space which restricts to the uniform distribution in all k-sets. Previous work on small spaces with limited independence focused on providing independence or near-independence in every k-set of the universe.

We show how to construct the sample spaces efficiently both sequentially and in parallel. In case there are polynomially many (in m) neighborhoods, each of size O(log m), the parallel construction is in NC.

These spaces provide a new derandomization technique for algorithms; particularly, algorithms related to the Lova´sz local lemma. We also describe applications to the exhaustive testing of VLSI circuits, and to coding for burst errors on noisy channels.