Revision #1 Authors: Valentine Kabanets, Russell Impagliazzo

Accepted on: 26th February 2003 00:00

Downloads: 2830

Keywords:

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.

TR02-055 Authors: Valentine Kabanets, Russell Impagliazzo

Publication: 20th September 2002 11:04

Downloads: 3205

Keywords:

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.