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

derandomizationpolynomial identity testingcircuit lower bounds

Mathematics Subject Classification ID

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

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)

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

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)