@inproceedings{10.1145/780542.780595,
    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 ⊄ 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⊆ ∩ε > 0NTIME(2(nε)), 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.},
    Address = {New York, NY, USA},
    Author = {Kabanets, Valentine and Impagliazzo, Russell},
    BookTitle = {Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing},
    File = {DERANDOMIZING POLYNOMIAL IDENTITY TESTS MEANS PROVING CIRCUIT LOWER BOUNDS - kabanets2004.pdf},
    ISBN = {1581136749},
    Keywords = {derandomization, NEXP, BPP, polynomial identity testing, circuit lower bounds},
    Location = {San Diego, CA, USA},
    Pages = {355--364},
    Publisher = {Association for Computing Machinery},
    Series = {STOC '03},
    Title = {Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds},
    URL = {https://doi.org/10.1145/780542.780595},
    Year = {2003},
    bdsk-url-1 = {https://doi.org/10.1145/780542.780595},
    date-added = {2021-10-08 16:15:11 +0200},
    date-modified = {2021-10-08 16:15:11 +0200},
    file-2 = {Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds ContactAdd CommentRSS-Feed - Revision1OfTR02-055.pdf},
    numpages = {10},
    doi = {10.1145/780542.780595}
}

@inproceedings{10.1145/780542.780595, 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 ⊄ 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⊆ ∩ε > 0NTIME(2(nε)), 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.}, Address = {New York, NY, USA}, Author = {Kabanets, Valentine and Impagliazzo, Russell}, BookTitle = {Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing}, File = {DERANDOMIZING POLYNOMIAL IDENTITY TESTS MEANS PROVING CIRCUIT LOWER BOUNDS - kabanets2004.pdf}, ISBN = {1581136749}, Keywords = {derandomization, NEXP, BPP, polynomial identity testing, circuit lower bounds}, Location = {San Diego, CA, USA}, Pages = {355--364}, Publisher = {Association for Computing Machinery}, Series = {STOC '03}, Title = {Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds}, URL = {https://doi.org/10.1145/780542.780595}, Year = {2003}, bdsk-url-1 = {https://doi.org/10.1145/780542.780595}, date-added = {2021-10-08 16:15:11 +0200}, date-modified = {2021-10-08 16:15:11 +0200}, file-2 = {Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds ContactAdd CommentRSS-Feed - Revision1OfTR02-055.pdf}, numpages = {10}, doi = {10.1145/780542.780595} }