Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-119 | 9th September 2019 20:11

On Hitting-Set Generators for Polynomials that Vanish Rarely


Authors: Dean Doron, Amnon Ta-Shma, Roei Tell
Publication: 15th September 2019 17:51
Downloads: 105


We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was first asked by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for an application, and another specific setting was later studied by the third author (CCC 2017).

In this work our main interest is a *systematic study of the problem itself*, in its general form, and we prove results that significantly extend and improve the two previously-known results. Our contributions are of two types:

1. Over fields of size $2\le|\mathbb{F}|\le poly(n)$, we show that the seed length of any hitting-set generator for polynomials of degree $d\le n^{.49}$ that vanish on at most $\epsilon=|\mathbb{F}|^{-t}$ of their inputs is at least $\Omega\left((d/t)\cdot\log(n)\right)$.

2. Over $\mathbb{F}_2$, we show that there exists a (non-explicit) hitting-set generator for polynomials of degree $d\le n^{.99}$ that vanish on at most $\epsilon=|\mathbb{F}|^{-t}$ of their inputs with seed length $O\left((d-t)\cdot\log(n)\right)$. We also show a polynomial-time computable hitting-set generator with seed length $O\left( (d-t)\cdot\left(2^{d-t}+\log(n)\right) \right)$.

In addition, we prove that the problem we study is closely related to the following question: ``Does there exist a small set $S\subseteq\mathbb{F}^n$ whose degree-$d$ closure is very large?'', where the degree-$d$ closure of $S$ is the variety induced by the set of degree-$d$ polynomials that vanish on $S$. We then use our lower bounds on hitting-sets for polynomials that vanish rarely to deduce lower bounds for this question.

ISSN 1433-8092 | Imprint