Natural Proofs versus Derandomization

DOI10.1137/130938219zbMath1339.68101arXiv1212.1891OpenAlexW2343516500WikidataQ113779157 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 boundscircuit complexityderandomizationnondeterminismrandomized computationACCnatural proofs

Mathematics Subject Classification ID

Related Items (17)

Local Reductions ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Local reduction ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Average-case rigidity lower bounds

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

This page was built for publication: Natural Proofs versus Derandomization