Natural Proofs versus Derandomization

DOI10.1137/130938219zbMath1339.68101arXiv1212.1891WikidataQ113779157 ScholiaQ113779157MaRDI QIDQ2805512

R. Ryan Williams

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

zbMATH Keywords

lower bounds; circuit complexity; derandomization; nondeterminism; randomized computation; ACC; natural proofs

Mathematics Subject Classification ID

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, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Hardness magnification near state-of-the-art lower bounds, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Local reduction, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Average-case rigidity lower bounds, Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)], Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, 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