Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-119 | 6th January 2020 14:10

On Hitting-Set Generators for Polynomials that Vanish Rarely

RSS-Feed




Revision #1
Authors: Dean Doron, Amnon Ta-Shma, Roei Tell
Accepted on: 6th January 2020 14:10
Downloads: 76
Keywords: 


Abstract:

The problem of constructing hitting-set generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: 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 considered by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for a particular 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 relaxed problem*, in its general form, and we prove results that significantly improve and extend the two previously-known results. Our contributions are of two types:
\begin{itemize}
\item Over fields of size $2\le|\mathbb{F}|\le\mathrm{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)$.
\item 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)$.
\end{itemize}

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$.



Changes to previous version:

Improved our lower bounds (by removing the requirement on the HSG's density), added refs to previous works on degree-d closures, and added an appendix with an alternative proof approach for our lower bounds.


Paper:

TR19-119 | 9th September 2019 20:11

On Hitting-Set Generators for Polynomials that Vanish Rarely





TR19-119
Authors: Dean Doron, Amnon Ta-Shma, Roei Tell
Publication: 15th September 2019 17:51
Downloads: 173
Keywords: 


Abstract:

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