Theory of Computing
-------------------
Title     : Optimal Hitting Sets for Combinatorial Shapes
Authors   : Aditya Bhaskara, Devendra Desai, and Srikanth Srinivasan
Volume    : 9
Number    : 13
Pages     : 441-470
URL       : https://theoryofcomputing.org/articles/v009a013

Abstract
--------

We consider the problem of constructing explicit Hitting Sets for
_combinatorial shapes_, a class of statistical tests first studied by
Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize
many well-studied classes of tests, including symmetric functions and
combinatorial rectangles. Generalizing results of Linial, Luby, Saks,
and Zuckerman (Combinatorica 1997) and Rabani and Shpilka (SICOMP
2010), we construct explicit hitting sets for combinatorial shapes of
size polynomial in the alphabet size, dimension, and the inverse of
the error parameter. This is optimal up to polynomial factors. The
best previous hitting sets came from the pseudorandom generator
construction of Gopalan et al., and in particular had size that was
quasipolynomial in the inverse of the error parameter.

Our construction builds on natural variants of the constructions of
Linial et al. and Rabani and Shpilka. In the process, we construct
fractional perfect hash families and hitting sets for combinatorial
rectangles with stronger guarantees. These might be of independent
interest.

An earlier version of this paper appeared in the Proceedings of
the 16th International Workshop on Randomization and Computation
(RANDOM 2012), pp. 423-434, Springer 2012.