Natural proofs versus derandomization

DOI10.1137/130938219zbMATH Open1339.68101arXiv1212.1891OpenAlexW2343516500WikidataQ113779157 ScholiaQ113779157MaRDI QIDQ2805512FDOQ2805512

Authors: Ryan Williams 

Publication date: 12 May 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as $sfNEXPotsubsetsfT{C}^0$. Natural Proofs have three properties: they are constructive (an efficient algorithm $A$ is embedded in them), have largeness ($A$ accepts a large fraction of strings), and are useful ($A$ rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are "naturalizing" would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable: largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove: $$ Constructivity is unavoidable, even for $sfNEXP$ lower bounds. Informally, we prove for all "typical" non-uniform circuit classes $calC$, $sfNEXPotsubsetcalC$ if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by $calC$-circuits. Hence $sfNEXPotsubsetcalC$ is equivalent to exhibiting a constructive property useful against $calC$. $$ There are no $sfP$-natural properties useful against $calC$ if and only if randomized exponential time can be "derandomized" using truth tables of circuits from $calC$ as random seeds. Therefore the task of proving there are no $sfP$-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results, including improved ${sfACC}^0$ lower bounds and new unconditional derandomizations.

Full work available at URL: https://arxiv.org/abs/1212.1891

Recommendations

• Natural proofs versus derandomization
• Natural proofs
• Almost-natural proofs
• Natural proofs
• Derandomizing polynomial identity tests means proving circuit lower bounds

zbMATH Keywords

lower boundsderandomizationnondeterminismcircuit complexityACCrandomized computationnatural proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Computational Complexity
• Almost-natural proofs
• Hardness vs randomness
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• On ACC
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Randomness vs time: Derandomization under a uniform assumption
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Hardness Amplification Proofs Require Majority
• Natural proofs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Number-theoretic constructions of efficient pseudo-random functions
• Unbounded fan-in circuits and associative functions
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudo-random generators for all hardnesses
• Title not available (Why is that?)
• Easiness assumptions and hardness tests: Trading time for zero error
• Circuit minimization problem
• A Turing machine time hierarchy
• Title not available (Why is that?)
• Power from Random Strings
• Title not available (Why is that?)
• Some observations on the probabilistic algorithms and NP-hard problems
• Unconditional Lower Bounds against Advice
• Improving exhaustive search implies superpolynomial lower bounds
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Hierarchies for semantic classes
• The circuit-input game, natural proofs, and testing circuits with data
• Pseudorandom functions in \(\text{TC}^0\) and cryptographic limitations to proving lower bounds
• Substitution-permutation networks, pseudorandom functions, and natural proofs
• Stronger lower bounds and randomness-hardness trade-offs using associated algebraic complexity classes

Cited In (27)

• Expander-Based Cryptography Meets Natural Proofs
• Mining circuit lower bound proofs for meta-algorithms
• Natural proofs
• Constructive separations and their consequences
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Almost-natural proofs
• Average-case rigidity lower bounds
• What is \dots a natural proof?
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• New algorithms and lower bounds for circuits with linear threshold gates
• Local reduction
• Natural proofs
• Unifying known lower bounds via geometric complexity theory
• Towards hardness of approximation for polynomial time problems
• Circuit lower bounds from learning-theoretic approaches
• Natural proofs versus derandomization
• Rigid matrices from rectangular PCPs
• The circuit-input game, natural proofs, and testing circuits with data
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Hardness magnification near state-of-the-art lower bounds
• Title not available (Why is that?)
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Local reductions

This page was built for publication: Natural proofs versus derandomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805512)