Derandomizing polynomial identity tests means proving circuit lower bounds

DOI10.1145/780542.780595zbMath1192.94144OpenAlexW2123852216MaRDI QIDQ5901092

Valentine Kabanets, Russell Impagliazzo

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780595

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Analytic circuit theory (94C05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Classical complexity and quantum entanglement, Subexponential size hitting sets for bounded depth multilinear formulas, Ideals of spaces of degenerate matrices, Exact learning from an honest teacher that answers membership queries, Arithmetic Circuits, Monomial Algebras and Finite Automata, A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing, On testing monomials in multivariate polynomials, Unnamed Item, Hardness of graph-structured algebraic and symbolic problems, Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials, A case of depth-3 identity testing, sparse factorization and duality, Unnamed Item, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, The Monomial Ideal Membership Problem and Polynomial Identity Testing, Characterizing Valiant's algebraic complexity classes, The ideal membership problem and polynomial identity testing, Linear matroid intersection is in quasi-NC, Lower bounds for arithmetic circuits via the Hankel matrix, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Factorization of polynomials given by arithmetic branching programs