More Web Proxy on the site http://driver.im/

article

Derandomizing polynomial identity tests means proving circuit lower bounds

Authors:

Valentine Kabanets,

Russell ImpagliazzoAuthors Info & Claims

Computational Complexity, Volume 13, Issue 1/2

Pages 1 - 46

https://doi.org/10.1007/s00037-004-0182-6

Published: 01 December 2004 Publication History

Abstract

We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic 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 circuit of polynomially bounded degree computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If RP = P (or even coRP ⊆ ∩_{ε > 0} NTIME(2ⁿ^ε), 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.We also prove unconditionally that NEXP^RP does not have polynomial-size Boolean or arithmetic circuits. Finally, we show that NEXP ⊄ P/poly if both BPP = P and low-degree testing is in P; here 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.

References

[1]

M. AGRAWAL & S. BISWAS (2003). Primality and identity testing via Chinese remaindering. J. ACM50, 429-443 (preliminary version in FOCS'99).

[2]

M. AGRAWAL, N. KAYAL & N. SAXENA (2002). PRIMES is in P. Manuscript.

[3]

A. E. ANDREEV, A. E. F. CLEMENTI & J. D. P. ROLIM (1998). A new general derandomization method. J. ACM45, 179-213 (preliminary version in ICALP'96).

[4]

S. ARORA, C. LUND, R. MOTWANI, M. SUDAN & M. SZEGEDY (1998). Proof verification and the hardness of approximation problems. J. ACM45, 501-555 (preliminary version in FOCS'92).

[5]

S. ARORA & S. SAFRA (1998). Probabilistic checking of proofs: A new characterization of NP. J. ACM45, 70-122 (preliminary version in FOCS'92).

[6]

S. ARORA & M. SUDAN (1997). Improved low-degree testing and its applications. In Proc. 29th Annual ACM Symposium on Theory of Computing, 485-495.

[7]

L. BABAI (1985). Trading group theory for randomness. In Proc. 17th Annual ACM Symposium on Theory of Computing, 421-429.

[8]

L. BABAI, L. FORTNOW & C. LUND (1991). Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity1, 3-40.

[9]

L. BABAI, L. FORTNOW, N. NISAN & A. WIGDERSON (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complexity3, 307-318.

[10]

L. BABAI & S. MORAN (1988). Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. System Sci.36, 254-276.

Digital Library

[11]

D. BEAVER & J. FEIGENBAUM (1990). Hiding instances in multioracle queries. In Proc. 7th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 415, Springer, 37-48.

[12]

M. BLUM, A. K. CHANDRA & M. N. WEGMAN (1980). Equivalence of free Boolean graphs can be tested in polynomial time. Inform. Process. Lett.10, 80-82.

[13]

M. BLUM & S. KANNAN (1995). Designing programs that check their work. J. ACM42, 269-291.

[14]

R. BOPPANA & R. HIRSCHFELD (1989). Pseudo-random generators and complexity classes. In Randomness and Computation, S. Micali (ed.), Adv. Comput. Research 5, JAI Press, Greenwich, CT, 1-26.

[15]

R.P. BRENT (1974). The parallel evaluation of general arithmetic expressions. J. ACM21, 201-206.

[16]

H. BUHRMAN & L. FORTNOW (1999). One-sided versus two-sided error in probabilistic computation. In Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science, C. Meinel & S. Tison (eds.), Lecture Notes in Comput. Sci. 1563, Springer, 100-109.

[17]

H. BUHRMAN, L. FORTNOW & L. THIERAUF (1998). Nonrelativizing separations. In Proc. 13th Annual IEEE Conference on Computational Complexity, 8-12.

[18]

S. R. Buss, S. A. COOK, A. GUPTA & V. RAMACHANDRAN. (1992). An optimal parallel algorithm for formula evaluation. SIAM J. Comput.21, 755-780.

Digital Library

[19]

S. CHARI, P. ROHATGI & A. SRINIVASAN (1995). Randomness-optimal unique element isolation with applications to perfect matching and related problems. SIAM J. Comput.24, 1036-1050.

Digital Library

[20]

Z. CHEN & M. KAO (2000). Reducing randomness via irrational numbers. SIAM J. Comput.29, 1247-1256 (preliminary version in STOC'97).

Digital Library

[21]

A. L. CHISTOV (1985). Fast parallel evaluation of the rank of matrices over a field of arbitrary characteristic. In Fundamentals of Computation Theory, Lecture Notes in Comput. Sci. 199, Springer, 63-79.

[22]

M. CLAUSEN, A. DRESS, J. GRABMEIER & M. KARPINSKY (1991). On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoret. Comput. Sci.84, 151-164.

[23]

R. A. DEMILLO & R. J. LIPTON (1978). A probabilistic remark on algebraic program testing. Inform. Process. Lett.7, 193-195.

[24]

U. FEICE, S. GOLDWASSER, L. LOVÁSZ, S. SAFRA & M. SZECEDY (1996). Interactive proofs and the hardness of approximating cliques. J. ACM43, 268-292 (preliminary version in FOCS'91).

[25]

J. VON ZUR GATHEN (1987). Feasible arithmetic computations: Valiant's hypothesis. J. Symbolic Comput.4, 137-172.

Digital Library

[26]

P. GEMMELL & M. SUDAN (1992). Highly resilient correctors for multivariate polynomials. Inform. Process. Lett.43, 169-174.

Digital Library

[27]

O. GOLDREICH & D. ZUCKERMAN (1997). Another proof that BPP⊆⊆PH (and more). Electronic Colloq. Comput. ComplexityTR97-045.

[28]

D. Yu. GRIGORIEV, M. KARPINSKY & M. F. SINGER (1990). Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comput.19, 1059-1063.

Digital Library

[29]

O. H. IBARRA & S. MORAN (1983). Probabilistic algorithms for deciding equivalence of straight-line programs. J. ACM30, 217-228.

[30]

R. IMPAGLIAZZO, V. KABANETS & A. WIGDERSON (2002). In search of an easy witness: Exponential time vs. probabilistic polynomial time. J. Comput. System Sci.65, 672-694 (preliminary version in CCC'01).

Digital Library

[31]

R. IMPAGLIAZZO, R. SHALTIEL & A. WIGDERSON (1999). Near-optimal conversion of hardness into pseudo-randomness. In Proc. 40th Annual IEEE Symposium on Foundations of Computer Science, 181-190.

[32]

R. IMPAGLIAZZO, R. SHALTIEL & A. WIGDERSON (2000). Extractors and pseudo-random generators with optimal seed length. In Proc. 32nd Annual ACM Symposium on Theory of Computing, 1-10.

Digital Library

[33]

R. IMPAGLIAZZO & A. WIGDERSON (1997). P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proc. 29th Annual ACM Symposium on Theory of Computing, 220-229.

[34]

R. IMPAGLIAZZO & A. WIGDERSON (2001). Randomness vs time: Derandomization under a uniform assumption. J. Comput. System Sci.63, 672-688 (preliminary version in FOCS'98).

Digital Library

[35]

V. KABANETS (2001). Easiness assumptions and hardness tests: trading time for zero error. J. Comput. System Sci.63, 236-252 (preliminary version in CCC'00).

Digital Library

[36]

V. KABANETS, C. RACKOFF & S. COOK (2000). Efficiently approximable real-valued functions. Electronic Colloq. Comput. ComplexityTR00-034.

[37]

E. KALTOFEN (1988). Greatest common divisors of polynomials given by straight-line programs. J. ACM35, 231-264.

[38]

E. KALTOFEN (1989). Factorization of polynomials given by straight-line programs. In Randomness and Computation, S. Micali (ed.), Adv. Comput. Research 5, JAI Press, Greenwich, CT, 375-412.

[39]

E. KALTOFEN (1992). On computing determinants of matrices without divisions. In Proc. 1992 International Symposium on Symbolic and Algebraic Computation (ISSAC'92), P. S. Wang (ed.), 342-349.

[40]

A. KLIVANS & D. VAN MELKEBEEK (2002). Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput.31, 1501-1526 (preliminary version in STOC'99).

Digital Library

[41]

. KLIVANS & D. SPIELMAN (2001). Randomness efficient identity testing of multivariate polynomials. In Proc. 33rd Annual ACM Symposium on Theory of Computing, 216-223.

[42]

D. LEWIN & S. VADHAN (1998). Checking polynomial identities over any field: Towards a derandomization? In Proc. 30th Annual ACM Symposium on Theory of Computing, 438-447.

[43]

N. LINIAL, Y. MANSOUR & N. NISAN (1993). Constant depth circuits, Fourier transform and learnability, J. ACM40, 607-620.

[44]

R. LIPTON (1991). New directions in testing. In Distributed Computing and Cryptography, J. Feigenbaum & M. Merrit (eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 2, Amer. Math. Soc., 191-202.

[45]

L. LOVÁSZ (1979). On determinants, matchings and random algorithms. In Fundamentals of Comput. Theory, L. Budach (ed.), Akademie-Verlag, Berlin, 565-574.

[46]

C. LUND, L. FORTNOW, H. KARLOFF & N. NISAN (1992). Algebraic methods for interactive proof systems, J. ACM39, 859-868.

[47]

K. MULMULEY, U. VAZIRANI & V. VAZIRANI (1987). Matching is as easy as matrix inversion. Combinatorica7, 105-113.

[48]

N. NISAN & A. WIGDERSON (1994). Hardness vs. randomness, J. Comput. System Sci.49, 149-167.

Digital Library

[49]

C. H. PAPADIMITRIOU (1994). Computational Complexity. Addison-Wesley, Reading, MA.

[50]

R. PATURI, P. PUDLÁK, M.E. SAKS & F. ZANE (1998). An improved exponential-time algorithm for k-SAT. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science, 628-637.

[51]

R. PATURI, P. PUDLÁK & F. ZANE (1999). Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci., Article 11, 19 pp. (preliminary version in FOCS'97).

[52]

R. PATURI, M. E. SAKS & F. ZANE (2000). Exponential lower bounds for depth three Boolean circuits. Comput. Complexity9, 1-15 (preliminary version in STOC'97).

[53]

V. R. PRATT (1975). Every prime has a succinct certificate. SIAM J. Comput.4, 214-220.

Digital Library

[54]

R. RAZ, O. REINGOLD & S. P. VADHAN (2002). Extracting all the randomness and reducing the error in Trevisan's extractors. J. Comput. System Sci.65, 97-128 (preliminary version in STOC'99).

Digital Library

[55]

R. RAZ & S. SAFRA (1997). A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th Annual ACM Symposium on Theory of Computing, 475-484.

[56]

A. A. RAZBOROV & S. RUDICH (1997). Natural proofs. J. Comput. System Sci.55, 24-35.

Digital Library

[57]

R. M. ROTH & G. M. BENEDEK (1991). Interpolation and approximation of sparse multivariate polynomials. SIAM J. Comput.20, 291-314.

Digital Library

[58]

R. RUBINFELD & M. SUDAN (1996). Robust characterizations of polynomials with applications to program testing. SIAM J. Comput.25, 252-271.

Digital Library

[59]

J. T. SCHWARTZ (1980). Fast probabilistic algorithms for verification of polynomial identities. J. ACM27, 701-717.

[60]

R. SHALTIEL & C. UMANS (2001). Simple extractors for all min-entropies and a new pseudo-random generator. In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science, 648-657.

[61]

A. SHAMIR (1992). IP = PSPACE. J. ACM39, 869-877.

[62]

V. STRASSEN (1973). Vermeidung von Divisionen. J. Reine Angew. Math.264, 182-202.

[63]

M. SUDAN (1997). Decoding of Reed Solomon codes beyond the error-correction bound. J. Complexity13, 180-193.

[64]

M. SUDAN, L. TREVISAN & S. VADHAN (2001). Pseudorandom generators without the XOR lemma. J. Comput. System Sci.62, 236-266 (preliminary version in STOC'99).

Digital Library

[65]

S. TODA (1991). PP is as hard as the polynomial-time hierarchy. SIAM J. Comput.20, 865-877.

Digital Library

[66]

C. UMANS (2003). Pseudo-random generators for all hardnesses. J. Comput. System Sci.67, 419-440 (preliminary version in STOC'02).

Digital Library

[67]

L. VALIANT (1979a). Completeness classes in algebra. In Proc. 11th Annual ACM Symposium on Theory of Computing, 249-261.

[68]

L. VALIANT (1979b). The complexity of computing the permanent. Theoret. Comput. Sci.8, 189-201.

[69]

L. VALIANT & V. VAZIRANI (1986). NP is as easy as detecting unique solutions. Theoret. Comput. Sci.47, 85-93.

Digital Library

[70]

A.C. YAO (1982). Theory and applications of trapdoor functions. In Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, 80-91.

[71]

F. ZANE (1998). Circuits, CNFs, and Satisfiability. Ph.D. thesis, UCSD.

[72]

R.E. ZIPPEL (1979). Probabilistic algorithms for sparse polynomials. In Proc. International Symposium on Symbolic and Algebraic Manipulation (EUROSAM'79), Lecture Notes in Comput. Sci. 72, Springer 216-226.

Cited By

Saha CThankey B(2024)Hitting Sets for Orbits of Circuit Classes and Polynomial FamiliesACM Transactions on Computation Theory10.1145/366580016:3(1-50)Online publication date: 23-May-2024
https://dl.acm.org/doi/10.1145/3665800
Bhargav CDwivedi PSaxena NMohar BShinkar IO'Donnell R(2024)Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit FactoringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649743(130-140)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649743
Arvind VChatterjee AMukhopadhyay PMohar BShinkar IO'Donnell R(2024)Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649693(106-117)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649693
Show More Cited By

Index Terms

Derandomizing polynomial identity tests means proving circuit lower bounds

Recommendations

Derandomizing polynomial identity tests means proving circuit lower bounds
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

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 ...
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are ...
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games
CCC '12: Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC)

Hardness against nondeterministic circuits is known to suffice for derandomizing Arthur-Merlin games. We show a result in the other direction - that hardness against nondeterministic circuits is *necessary* for derandomizing Arthur-Merlin games. In fact,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Complexity

Computational Complexity Volume 13, Issue 1/2

December 2004

89 pages

ISSN:1016-3328

Issue’s Table of Contents

Publisher

Birkhauser Verlag

Switzerland

Publication History

Published: 01 December 2004

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

134
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saha CThankey B(2024)Hitting Sets for Orbits of Circuit Classes and Polynomial FamiliesACM Transactions on Computation Theory10.1145/366580016:3(1-50)Online publication date: 23-May-2024
https://dl.acm.org/doi/10.1145/3665800
Bhargav CDwivedi PSaxena NMohar BShinkar IO'Donnell R(2024)Learning the Coefficients: A Presentable Version of Border Complexity and Applications to Circuit FactoringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649743(130-140)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649743
Arvind VChatterjee AMukhopadhyay PMohar BShinkar IO'Donnell R(2024)Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649693(106-117)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649693
Limaye NSrinivasan STavenas S(2024)Superpolynomial Lower Bounds Against Low-Depth Algebraic CircuitsCommunications of the ACM10.1145/361109467:2(101-108)Online publication date: 25-Jan-2024
https://dl.acm.org/doi/10.1145/3611094
Iwamasa Y(2024)A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with submatricesMathematical Programming: Series A and B10.1007/s10107-023-01949-1204:1-2(27-79)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10107-023-01949-1
Bhargava VSaraf SVolkovich ISaha BServedio R(2023)Linear Independence, Alternants, and ApplicationsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585149(441-454)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585149
Oki T(2023)Computing valuations of the Dieudonné determinantsJournal of Symbolic Computation10.1016/j.jsc.2022.10.010116:C(284-323)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.10.010
Bünz BFisch B(2023)Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct ArgumentsTheory of Cryptography10.1007/978-3-031-48621-0_14(394-423)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48621-0_14
Volk BKumar M(2022)A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear CircuitsACM Transactions on Computation Theory10.1145/354368514:2(1-14)Online publication date: 14-Sep-2022
https://dl.acm.org/doi/10.1145/3543685
Andrews RForbes MLeonardi SGupta A(2022)Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520025(389-402)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520025
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents