Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Nati Linial, Michael G. Luby, Michael Saks, David Zuckerman · 1993
Given d, m and c, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6.Both the running time of the algorithm and ISI are polynomial in m log(d) /c.This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.