Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension

We describe a deterministic algorithm which, on input integers d, m and real number ffl 2 (0; 1), produces a subset S of [m] d = f1; 2; 3; : : : ; mg d that hits every combinatorial rectangle in [m] d of volume at least ffl, i.e., every subset of [m] d the form R 1 \Theta R 2 \Theta : : : \Theta R d of size at least fflm d . The cardinality of S is polynomial in m(log d)=ffl, and the time to construct it is polynomial in md=ffl. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables. 1 Introduction This paper is motivated by the witness finding problem: design an efficient algorithm that on input a positive integer n and a real ffl ? 0 produces a list S of elements in f0; 1g n such that, for any witness set R ` f0; 1g n where jRj=2 n ffl, S " R 6= ;. The running time of the algorithm should be polynomial in n and 1=ffl. This is a fundamental problem in complexity theory where ..