On circuit lower bounds from derandomization

DOI10.4086/TOC.2011.V007A012MaRDI QIDQ2913799zbMATH OpenOpenAlexFDO

Authors Scott Aaronson, Dieter Van Melkebeek

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a012

zbMATH Keywords

circuit lower boundsderandomizationpolynomial identity testing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Tighter connections between derandomization and circuit lower bounds
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Uniform derandomization from pathetic lower bounds

Cited in

(21)

• Circuit size relative to pseudorandom oracles
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• A zero-one law for RP and derandomization of AM if NP is not small
• On derandomizing Yao's weak-to-strong OWF construction
• Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
• Uniform derandomization from pathetic lower bounds
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Uniform Derandomization from Pathetic Lower Bounds
• Pseudorandom generators for combinatorial checkerboards
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A Wronskian approach to the real \(\tau\)-conjecture
• On uniformity and circuit lower bounds
• Mathematical Foundations of Computer Science 2004
• Tighter connections between derandomization and circuit lower bounds
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• Hardness hypotheses, derandomization, and circuit complexity

This page was built for publication: On circuit lower bounds from derandomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913799)