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 #2 to TR19-065 | 7th August 2019 22:24

Derandomization from Algebraic Hardness

RSS-Feed




Revision #2
Authors: Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon
Accepted on: 7th August 2019 22:24
Downloads: 62
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Revision #1 to TR19-065 | 1st May 2019 09:06

Derandomization from Algebraic Hardness: Treading the Borders





Revision #1
Authors: Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon
Accepted on: 1st May 2019 09:06
Downloads: 164
Keywords: 


Abstract:

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.



Changes to previous version:

Attempting to fix broken hyperlinks


Paper:

TR19-065 | 1st May 2019 04:52

Derandomization from Algebraic Hardness: Treading the Borders


Abstract:

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.



ISSN 1433-8092 | Imprint