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

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.

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.