Natural proofs
From MaRDI portal
Publication:5906823
DOI10.1006/jcss.1997.1494zbMath0884.68055OpenAlexW2912080987WikidataQ55878547 ScholiaQ55878547MaRDI QIDQ5906823
Steven Rudich, Alexander A. Razborov
Publication date: 3 December 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1494
Related Items (93)
In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ Expander-based cryptography meets natural proofs ⋮ Adaptively secure distributed PRFs from LWE ⋮ Kolmogorov width of discrete linear spaces: an approach to matrix rigidity ⋮ Substitutions into propositional tautologies ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ The GGM Function Family Is a Weakly One-Way Family of Functions ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Minimizing nfa's and regular expressions ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Lower bounds for the circuit size of partially homogeneous polynomials ⋮ Zero knowledge and circuit minimization ⋮ Robust simulations and significant separations ⋮ Proofs of Work from worst-case assumptions ⋮ Block-symmetric polynomials correlate with parity better than symmetric ⋮ Non-isometric quantum error correction in gravity ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Physical portrayal of computational complexity ⋮ Towards NP-P via proof complexity and search ⋮ The power of natural properties as oracles ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ Expressive power of SQL. ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ More on average case vs approximation complexity ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ The Complexity of Complexity ⋮ On matrix rigidity and locally self-correctable codes ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Unnamed Item ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Turing machines and bimachines ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ A new proof of the weak pigeonhole principle ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Limits on alternation trading proofs for time-space lower bounds ⋮ Tautologies from Pseudo-Random Generators ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ The communication complexity of addition ⋮ Extremal properties of polynomial threshold functions ⋮ Quantum certificate complexity ⋮ Padded Polynomials, Their Cousins, and Geometric Complexity Theory ⋮ Resource-bounded measure on probabilistic classes ⋮ The complexity of explicit constructions ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Using the renormalization group to classify Boolean functions ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\) ⋮ Pseudorandom generators without the XOR lemma ⋮ On the complexity of matrix rank and rigidity ⋮ Almost-natural proofs ⋮ Independence results for variants of sharply bounded induction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Easiness assumptions and hardness tests: Trading time for zero error ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ The non-hardness of approximating circuit size ⋮ Natural Proofs versus Derandomization ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Adaptively secure distributed PRFs from \(\mathsf{LWE}\) ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ On Negations in Boolean Networks ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Time-space tradeoffs for satisfiability ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ On converting CNF to DNF ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Unifying known lower bounds via geometric complexity theory ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom bits for constant depth circuits
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on monotone complexity of the logical permanent
- The monotone circuit complexity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
- The expressive power of voting polynomials
- The gap between monotone and non-monotone circuit complexity is exponential
- Efficient cryptographic schemes provably as secure as subset sum
- Parity, circuits, and the polynomial-time hierarchy
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Monotone circuits for matching require linear depth
- The Shrinkage Exponent of de Morgan Formulas is 2
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: Natural proofs
