A hitting-set generator (HSG) is a polynomial map $G:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ G$ is nonzero.
In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness.
Formally, we prove the following result over any field of characteristic zero:

Let $k\in \mathbb{N}$ and $\delta > 0$ be arbitrary constants. Suppose $\{P_d\}_{d\in \mathbb{N}}$ is an explicit family of $k$-variate polynomials such that $\operatorname{deg} P_d = d$ and $P_d$ requires algebraic circuits of size $d^\delta$. Then, there are explicit hitting sets of polynomial size for the class $\mathsf{VP}$.

This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps, our construction is purely algebraic and does \emph{not} rely on the notion of combinatorial designs.

As a direct consequence, we show that even saving \emph{a single point} from the ``trivial'' explicit, exponential sized hitting sets for constant-variate polynomials of low \emph{individual-degree} which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following:

Let $k\in \mathbb{N}$ and $\delta > 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of \emph{individual degree} $s$ that are computable by size $s^\delta$ circuits. Then there is an explicit hitting set of size $\operatorname{poly}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits.

As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $\tau$-Conjecture of Shub and Smale is true.

Incorporating some reviewer comments, strengthening theorems to construct HSG from any k-variate lower bound for slow-growign k, connection to Tau conjecture.

A hitting-set generator (HSG) is a polynomial map $G:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ G$ is nonzero.
In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness.
Formally, we prove the following result over any field $\mathbb{F}$ of characteristic zero:

Suppose $P(z_1,\ldots, z_k)$ is an explicit $k$-variate degree $d$ polynomial that is not computable by circuits of size $s$. Then, there is an explicit HSG $G_P:\mathbb{F}^{2k} \rightarrow \mathbb{F}^n$ such that every nonzero $n$-variate degree $D$ polynomial $C(\mathbf{x})$ computable by circuits of size $s'$ circuits satisfies $C \neq 0 \Rightarrow C \circ G_P \neq 0$, if $O(n^{10k}d^3 D s')< s$.

This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps, our construction is purely algebraic and does not rely on the notion of combinatorial designs.

As a direct consequence, we show that even saving a single point from the ``trivial'' explicit, exponential sized hitting sets for constant-variate polynomials of low individual-degree which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following:

Let $k$ be a large enough constant. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s$ circuits. Then there is an explicit hitting set of size $s^{O(k^2)}$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits.

The hardness requirement does not require border complexity. Also, the bootstrapping phenomenon for PIT is improved by weakening the hypothesis to saving one point from the trivial hitting set.

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ Gen$ is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field $\mathbb{F}$:

Suppose $P(z_1,\ldots, z_k)$ is an explicit $k$-variate degree $d$ polynomial that is not in the border of circuits of size $s$. Then, there is an explicit hitting-set generator $Gen_P:\mathbb{F}^{2k} \rightarrow \mathbb{F}^n$ such that every non-zero $n$-variate degree $D$ polynomial $Q(x_1, x_2, \ldots, x_n)$ in the border of size $s'$ circuits satisfies $Q \neq 0 \Rightarrow Q \circ Gen_P \neq 0$, provided $n^{10k}d D s' \leq s$.

This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption.

As a direct consequence, we show that even a slightly non-trivial explicit construction of hitting sets for polynomials in the border of constant-variate circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we prove the following theorem:

Let $\delta > 0$ be any constant and $k$ be a large enough constant. Suppose, for every $s \geq k$, there is an explicit hitting set of size $s^{k-\delta}$ for all degree $s$ polynomials in the border of $k$-variate size $s$ algebraic circuits. Then, there is an explicit hitting set of size $poly(s)$ for the border $s$-variate algebraic circuits of size $s$ and degree $s$.

Unlike the prior constructions of such maps [NW94, KI04, AGS18, KST19], our construction is purely algebraic and does not rely on the notion of combinatorial designs.

Attempting to fix broken hyperlinks

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ Gen$ is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field $\mathbb{F}$:

Suppose $P(z_1,\ldots, z_k)$ is an explicit $k$-variate degree $d$ polynomial that is not in the border of circuits of size $s$. Then, there is an explicit hitting-set generator $Gen_P:\mathbb{F}^{2k} \rightarrow \mathbb{F}^n$ such that every non-zero $n$-variate degree $D$ polynomial $Q(x_1, x_2, \ldots, x_n)$ in the border of size $s'$ circuits satisfies $Q \neq 0 \Rightarrow Q \circ Gen_P \neq 0$, provided $n^{10k}d D s' \leq s$.

This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption.

As a direct consequence, we show that even a slightly non-trivial explicit construction of hitting sets for polynomials in the border of constant-variate circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we prove the following theorem:

Let $\delta > 0$ be any constant and $k$ be a large enough constant. Suppose, for every $s \geq k$, there is an explicit hitting set of size $s^{k-\delta}$ for all degree $s$ polynomials in the border of $k$-variate size $s$ algebraic circuits. Then, there is an explicit hitting set of size $poly(s)$ for the border $s$-variate algebraic circuits of size $s$ and degree $s$.

Unlike the prior constructions of such maps [NW94, KI04, AGS18, KST19], our construction is purely algebraic and does not rely on the notion of combinatorial designs.