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 TR02-055 | 26th February 2003 00:00

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

RSS-Feed




Revision #1
Authors: Valentine Kabanets, Russell Impagliazzo
Accepted on: 26th February 2003 00:00
Downloads: 1808
Keywords: 


Abstract:

We show that derandomizing Polynomial Identity Testing is,
essentially, equivalent to proving circuit lower bounds for
NEXP. More precisely, we prove that if one can test in polynomial
time (or, even, nondeterministic subexponential time, infinitely
often) whether a given arithmetic circuit over integers computes an
identically zero polynomial, then either (i)
NEXP\not\subset P/poly or (ii) Permanent is not computable by
polynomial-size arithmetic circuits. We also prove a (partial)
converse: If Permanent requires superpolynomial-size arithmetic
circuits, then one can test in subexponential time whether a given
arithmetic formula computes an identically zero polynomial.

Since Polynomial Identity Testing is a coRP problem, we obtain the
following corollary: If RP=P (or, even,
coRP\subseteq\cap_{\epsilon>0} NTIME(2^{n^{epsilon}}), infinitely
often), then NEXP is not computable by polynomial-size arithmetic
circuits. Thus, establishing that RP=coRP or BPP=P would
require proving superpolynomial lower bounds for Boolean or arithmetic
circuits. We also show that any derandomization of RNC would yield
new circuit lower bounds for a language in NEXP.

Our techniques allow us to prove an unconditional circuit lower bound
for a language in NEXP^{RP}: we prove that either (i) Permanent is not
computable by polynomial-size arithmetic circuits, or (ii)
NEXP^{RP}\not\subset P/poly.

Finally, we prove that NEXP\not\subset P/poly if both
BPP=P and the low-degree testing is in P; here, the low-degree
testing is the problem of checking whether a given Boolean circuit
computes a function that is close to some low-degree polynomial over a
finite field.


Paper:

TR02-055 | 13th September 2002 00:00

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds





TR02-055
Authors: Valentine Kabanets, Russell Impagliazzo
Publication: 20th September 2002 11:04
Downloads: 1716
Keywords: 


Abstract:

We show that derandomizing Polynomial Identity Testing is,
essentially, equivalent to proving circuit lower bounds for
NEXP. More precisely, we prove that if one can test in polynomial
time (or, even, nondeterministic subexponential time, infinitely
often) whether a given arithmetic circuit over integers computes an
identically zero polynomial, then either (i)
NEXP\not\subset P/poly or (ii) Permanent is not computable by
polynomial-size arithmetic circuits. We also prove a (partial)
converse: If Permanent requires superpolynomial-size arithmetic
circuits, then one can test in subexponential time whether a given
arithmetic formula computes an identically zero polynomial.

Since Polynomial Identity Testing is a coRP problem, we obtain
the following corollary: If RP=P (or, even,
coRP\subseteq\cap_{\epsilon>0} NTIME(2^{n^{\epsilon}}), infinitely
often), then NEXP is not computable by polynomial-size arithmetic
circuits. Thus, establishing that RP=coRP or BPP=P would
require proving superpolynomial lower bounds for Boolean or arithmetic
circuits.

Our techniques allow us to prove an unconditional circuit lower bound
for a language in NEXP^{RP}: we prove that either (i) Permanent is not
computable by polynomial-size arithmetic circuits, or (ii)
NEXP^{RP}\not\subset P/poly.

Finally, we prove that NEXP\not\subset P/poly if both
BPP=P and the low-degree testing is in P; here, the low-degree
testing is the problem of checking whether a given Boolean circuit
computes a function that is close to some low-degree polynomial over a
finite field.



ISSN 1433-8092 | Imprint