Natural Proofs versus Derandomization
From MaRDI portal
Publication:2805512
DOI10.1137/130938219zbMath1339.68101arXiv1212.1891OpenAlexW2343516500WikidataQ113779157 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
