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-065 | 1st May 2019 09:06

Derandomization from Algebraic Hardness: Treading the Borders

RSS-Feed




Revision #1
Authors: Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon
Accepted on: 1st May 2019 09:06
Downloads: 112
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