Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

By Valentine Kabanets, Russell Impagliazzo. Symposium on the Theory of Computing, 2003

572 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/15400730c04b3d4c3d93024ff866aa4a1db09377

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Arithmetic Circuits: A survey of recent results and open questions (2010, background): “Recently, it was discovered that this problem is strongly related to the question of proving lower bounds [69].”
Classical complexity and quantum entanglement (2004, background): “Moreover, in light of the recent breakthrough paper [24] and Valiant’s result [31] on universality of symbolic determinants, the deterministic complexity of Edmonds’ problem has become fundamentally important in theoretical computer science.”
Classical deterministic complexity of Edmonds' Problem and quantum entanglement (2003, background): “It turns out that one of the most important cases when Edmonds problem can be solved in polynomial deterministic time, i.e. an intersection of two geometric matroids, corresponds to unentangled (aka separable ) bipartite density matrices.”
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time (2011, unknown): “The two methods do not differ much in their consequences: Both use the same number of random bits, and the challenge of giving a full derandomization seems to be equally difficult for both methods [1], [28].”
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, unknown): “PIT (equivalently, EquSLP) can be decided in co-RP, but no NP algorithm is known for it, and in fact an NP upper bound would yield as a consequence difficult lower bounds (see [35]).”
Fast Polynomial Factorization and Modular Composition (2011, background): “A purely algebraic algorithm carries some aesthetic appeal, and could be important in settings where one is working in an arithmetic model of computation (see, e.g., the pseudo-random generator of [KI04] for an example involving polynomial factorization).”
Handbook of Finite Fields (2013, background): “The construction, however, plays a key role in complexity theory [Kabanets and Impagliazzo 2004].”
Non-uniform ACC Circuit Lower Bounds (2011, background): “Kabanets and Impagliazzo [ KI04 ] proved that NEXP RP either doesn’t have polynomial size Boolean cir-”