On circuit lower bounds from derandomization
DOI10.4086/TOC.2011.V007A012zbMATH Open1247.68091OpenAlexW2183978808MaRDI QIDQ2913799FDOQ2913799
Authors: Scott Aaronson, Dieter Van Melkebeek 
Publication date: 27 September 2012
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2011.v007a012
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
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)
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
- Title not available (Why is that?)
- 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
- Uniform Derandomization from Pathetic Lower Bounds
- Circuit size relative to pseudorandom oracles
- Mathematical Foundations of Computer Science 2004
- Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits
- A Wronskian approach to the real \(\tau\)-conjecture
- Title not available (Why is that?)
- Deterministic polynomial identity tests for multilinear bounded-read formulae
- 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)
