RECORD
Derandomization from Algebraic Hardness
Computational Complexity · Submitted 30 Apr 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 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 $\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. 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\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 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.06 | 0.02 | asserted 0.98 |
| s1 | In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. | contribution 1.00 | 0.96 | 0.30 | asserted 1.00 |
| s2 | Formally, we prove the following over any field of characteristic zero: Let $k\in \mathbb{N}$ and $\delta > 0$ be arbitrary constants. | result 0.48 | 0.34 | 0.04 | asserted 0.67 |
| s3 | 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$. | contribution 0.42 | 0.15 | 0.05 | asserted 0.81 |
| s4 | Then, there are explicit hitting sets of polynomial size for $\mathsf{VP}$. | result 0.97 | 0.88 | 0.66 | asserted 1.00 |
| s5 | 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. | interpretation 0.55 | 0.91 | 0.62 | asserted 1.00 |
| s6 | 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. | result 0.59 | 0.92 | 0.11 | asserted 1.00 |
| s7 | More precisely, we show the following: Let $k\in \mathbb{N}$ and $\delta > 0$ be arbitrary constants. | contribution 0.49 | 0.76 | 0.04 | unclear 0.73 |
| s8 | 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^\delta$ circuits. | result 0.68 | 0.24 | 0.05 | asserted 0.78 |
| s9 | 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. | result 0.99 | 0.90 | 0.13 | asserted 1.00 |
| s10 | 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. | result 0.79 | 0.90 | 0.11 | asserted 0.52 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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 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 $\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. 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\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 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.
Human review
How the literature uses it
2 arXiv papers cite this in 4 sentences
Papers citing it · 1 sentence without a confident label
Uses its method or tool 1 paper
-
However, this recovery step happens to be a special case of similar step in the recent work of Guo, Kumar, Saptharishi and Solomon [ref] and we adapt their algorithm to our setting.
Decoding Multivariate Multiplicity Codes on Product Sets · Background and motivation for our algorithm · 0.96
Compares with it 1 paper
-
As a consequence, the details of this step are much simpler here, when compared to that in [ref] .
Decoding Multivariate Multiplicity Codes on Product Sets · Solving the equation to recover all close enough codewords · 1.00
Cites it as background 1 paper
-
Among examples of such results are the results on polynomial factorization [ref] , results on list decoding of multiplicity codes [ref] and hardness-randomness tradeoffs in algebraic complexity [ref] .
An Improved Line-Point Low-Degree Test · Bivariate low-degree tests · 0.86
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.