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.

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.