Natural Proofs versus Derandomization
From MaRDI portal
DOI10.1137/130938219zbMath1339.68101arXiv1212.1891WikidataQ113779157 ScholiaQ113779157MaRDI QIDQ2805512
Publication date: 12 May 2016
Published in: SIAM Journal on Computing, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.1891
lower bounds; circuit complexity; derandomization; nondeterminism; randomized computation; ACC; natural proofs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
Unnamed Item, Unnamed Item, New algorithms and lower bounds for circuits with linear threshold gates, Local reduction, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Mining circuit lower bound proofs for meta-algorithms, Unifying known lower bounds via geometric complexity theory, Circuit lower bounds from learning-theoretic approaches, Local Reductions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Almost-natural proofs
- Unbounded fan-in circuits and associative functions
- Some observations on the probabilistic algorithms and NP-hard problems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- On ACC
- Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
- Randomness vs time: Derandomization under a uniform assumption
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Number-theoretic constructions of efficient pseudo-random functions
- Circuit minimization problem
- Hierarchies for semantic classes
- Unconditional Lower Bounds against Advice
- Computational Complexity
- Hardness Amplification Proofs Require Majority
- Power from Random Strings
- Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs
- Natural proofs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Easiness assumptions and hardness tests: Trading time for zero error
