ECCC-Report TR19-065https://eccc.weizmann.ac.il/report/2019/065Comments and Revisions published for TR19-065en-usFri, 26 Jun 2020 09:00:18 +0300
Revision 3
| Derandomization from Algebraic Hardness: Treading the Borders |
Zeyu Guo,
Mrinal Kumar,
Ramprasad Saptharishi,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/065#revision3A 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.
Fri, 26 Jun 2020 09:00:18 +0300https://eccc.weizmann.ac.il/report/2019/065#revision3
Revision 2
| Derandomization from Algebraic Hardness |
Zeyu Guo,
Mrinal Kumar,
Ramprasad Saptharishi,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/065#revision2A 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.
Wed, 07 Aug 2019 22:24:28 +0300https://eccc.weizmann.ac.il/report/2019/065#revision2
Revision 1
| Derandomization from Algebraic Hardness: Treading the Borders |
Mrinal Kumar,
Ramprasad Saptharishi,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/065#revision1A 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.Wed, 01 May 2019 09:06:52 +0300https://eccc.weizmann.ac.il/report/2019/065#revision1
Paper TR19-065
| Derandomization from Algebraic Hardness: Treading the Borders |
Mrinal Kumar,
Ramprasad Saptharishi,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/065A 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.Wed, 01 May 2019 08:54:23 +0300https://eccc.weizmann.ac.il/report/2019/065