We give a deterministic algorithm which, on input an integer n , collection \cal F of subsets of {1,2,\ldots,n} , and ϵ∈ (0,1) , runs in time polynomial in n| \cal F |/ϵ and produces a \pm 1 ‐matrix M with n columns and m=O(log | \cal F |/ϵ
2
) rows with the following property: for any subset F ∈ \cal F , the fraction of 1's in the n ‐vector obtained by coordinatewise multiplication of the column vectors indexed by F is between (1-ϵ)/2 and (1+ϵ)/2 . In the case that \cal 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/?ϵ
2
) , compared with the best previous constructions in [NN] and [AGHP] which were, respectively, O(log n/ϵ
4
) and O(log
2
n/ϵ
2
) . 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.
