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 ∈ ∃ (0,1) runs in time polynomial in n‖f‖/∈ and produces a ±1-matrix M with n columns and m=O(log ‖f‖/∈²) rows with the following property: for any subset F ∃ f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1−∈)/2 and (1+∈)/2. In the case that f is the set of all subsets of size at most k, k constant, this gives a polynomial time construction for a k-wise ∈-biased sample space of size O(log n/∈ ²), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/∈ ⁴) and O((log n)²/∈ ²). The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files.