Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Markus Bläser: Asymptotically Optimal Hitting Sets Against Polynomials

Nov. 22, 2007, 10:15 a.m.
E 1 3, Room 415

Our main result is an efficient construction of a hitting set generator against the class of polynomials of degree $d_i$ in the $i$-th variable. The seed length of this generator is $\log D+\tilde{O}(\log^{1/2}D)$. Here, $\log D=\sum_i \log(d_i+1)$ is a lower bound bound on the seed length of any hitting set generator against this class. Our construction is the first to achieve asymptotically optimal seed length for every choice of the parameters $d_i$. In fact, we present a nearly linear time construction with this asymptotic guarantee. Furthermore, our results extend to classes of polynomials parameterized by upper bounds on the number of nonzero terms in each variable.

Underlying all of our constructions is a general and novel framework that exploits the product structure common to the classes of polynomials we consider. This framework allows us to obtain efficient and asymptotically optimal hitting set generators from primitives that need not be optimal or efficient by themselves.

Finally, our results imply blackbox polynomial identity tests that use fewer random bits than previous methods.

Joint work with Moritz Hardt and David Steurer.