Sample spaces with small bias on neighborhoods and error-correcting communication protocols

We give a deterministic algorithm which, on input an integer n, collection F of subsets of {1.2.....n}, and epsilon is an element of (0, 1), runs in t ime polynomial in n\F\/epsilon and produces a +/- 1-matrix M with n columns and m = O(log\F\/epsilon (2)) rows With the following property: for any su bset F is an element of F, the fraction of 1's in the n-vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1 - epsilon)/2 and (1 + epsilon)/2. In the case that F is the set of all subsets of size at most k, k constant, this gives a polynomial rime constru ction for a k-wise epsilon -biased sample space of size O (log n/epsilon (2 )), compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/epsilon (4)) and O(log(2) n/epsilon (2)). The n umber of rows in the construction matches the upper bound given by the prob abilistic existence argument. Such constructions are of interest for derand omizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files.