Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

2004/12/01 by Valentine Kabanets, Russell Impagliazzo · 7 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms

paper · doi:10.1007/s00037-004-0182-6

crossref issued 2004/12/01 · crossref published 2004/12/01 · crossref published-print 2004/12/01 · openalex publication_date 2004/12/01 · crossref created 2004/12/29 · crossref deposited 2019/05/22 · openalex created_date 2025/10/10 · crossref indexed 2026/07/15 · openalex updated_date 2026/07/23

Citations

• Matching is as easy as matrix inversion
• P = BPP if E requires exponential circuits
• Algebraic methods for interactive proof systems
• Interactive proofs and the hardness of approximating cliques

Cited by

• On identity testing of tensors, low-rank recovery and compressed sensing
• Shallow Circuits with High-Powered Inputs
• Non-uniform ACC Circuit Lower Bounds
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• Deterministic Depth-4 PIT and Normalization
• Rank Bounds and PIT for Σ³ ΠΣΠ^d circuits via a non-linear Edelstein-Kelly theorem
• Russell Impagliazzo [wikipedia]