Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with polynomialidentity testing:
TR02-055 | 13th September 2002
Valentine Kabanets, Russell Impagliazzo

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint