Natural proofs
From MaRDI portal
Publication:5906823
DOI10.1006/JCSS.1997.1494zbMATH Open0884.68055OpenAlexW2912080987WikidataQ55878547 ScholiaQ55878547MaRDI QIDQ5906823FDOQ5906823
Authors: Steven Rudich, Alexander 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
Recommendations
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Title not available (Why is that?)
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The expressive power of voting polynomials
- Parity, circuits, and the polynomial-time hierarchy
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pseudorandom bits for constant depth circuits
- Efficient cryptographic schemes provably as secure as subset sum
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Shrinkage Exponent of de Morgan Formulas is 2
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Lower bounds on monotone complexity of the logical permanent
- The gap between monotone and non-monotone circuit complexity is exponential
- Title not available (Why is that?)
- Monotone circuits for matching require linear depth
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Title not available (Why is that?)
- Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Adaptively secure distributed PRFs from \(\mathsf{LWE}\)
- Title not available (Why is that?)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Lower bounds for invariant queries in logics with counting.
- Mining circuit lower bound proofs for meta-algorithms
- Natural proofs
- Block-symmetric polynomials correlate with parity better than symmetric
- Almost \(k\)-wise independence and hard Boolean functions.
- Expressive power of SQL.
- Extremal properties of polynomial threshold functions
- Physical portrayal of computational complexity
- Towards NP-P via proof complexity and search
- The Complexity of Complexity
- The complexity of explicit constructions
- Almost-natural proofs
- Models of lower-bounds proofs
- What is \dots a natural proof?
- Exponential lower bound for bounded depth circuits with few threshold gates
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Substitutions into propositional tautologies
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Adaptively secure distributed PRFs from LWE
- Agnostic Learning from Tolerant Natural Proofs
- Circuit lower bounds à la Kolmogorov
- More on average case vs approximation complexity
- Fast pseudorandom functions based on expander graphs
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Lower bounds for unrestricted Boolean circuits: open problems
- Kolmogorov width of discrete linear spaces: an approach to matrix rigidity
- Easiness assumptions and hardness tests: Trading time for zero error
- Amplifying lower bounds by means of self-reducibility
- On Negations in Boolean Networks
- On nonadaptive reductions to the set of random strings and its dense subsets
- Quantum certificate complexity
- Unprovability of circuit upper bounds in Cook's theory PV
- On matrix rigidity and locally self-correctable codes
- On the complexity of matrix rank and rigidity
- Pseudorandom generators without the XOR lemma
- Unifying known lower bounds via geometric complexity theory
- Nonuniform ACC circuit lower bounds
- Tautologies from pseudo-random generators
- On converting CNF to DNF
- Proofs of Work from worst-case assumptions
- A new proof of the weak pigeonhole principle
- Randomness vs time: Derandomization under a uniform assumption
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Lower bounds against weakly-uniform threshold circuits
- Minimizing nfa's and regular expressions
- Independence results for variants of sharply bounded induction
- The circuit-input game, natural proofs, and testing circuits with data
- Padded polynomials, their cousins, and geometric complexity theory
- The non-hardness of approximating circuit size
- Limits on alternation trading proofs for time-space lower bounds
- What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
- Turing machines and bimachines
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Hardness magnification near state-of-the-art lower bounds
- Title not available (Why is that?)
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
- Title not available (Why is that?)
- Title not available (Why is that?)
- Resource-bounded measure on probabilistic classes
- The communication complexity of addition
- Time-space tradeoffs for satisfiability
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Algebrization: a new barrier in complexity theory
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Title not available (Why is that?)
- Expander-Based Cryptography Meets Natural Proofs
- On the Symmetries of and Equivalence Test for Design Polynomials.
- Pseudo-derandomizing learning and approximation
- Title not available (Why is that?)
- Constructive separations and their consequences
- Zero knowledge and circuit minimization
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Paradigms for Unconditional Pseudorandom Generators
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Expander-based cryptography meets natural proofs
- Non-isometric quantum error correction in gravity
- Complexity barriers as independence
- Title not available (Why is that?)
- Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
- Lower bounds for the circuit size of partially homogeneous polynomials
- Using the renormalization group to classify Boolean functions
- The power of natural properties as oracles
- Localizability of the approximation method
- Hardness magnification near state-of-the-art lower bounds
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Computationally hard problems for logic programs under answer set semantics
- A direct PRF construction from Kolmogorov complexity
- Circuit lower bounds from learning-theoretic approaches
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Unifying lower bounds for algebraic machines, semantically
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- A homological theory of functions: nonuniform Boolean complexity separation and VC dimension bound via algebraic topology, and a homological Farkas lemma
- Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
- The GGM Function Family Is a Weakly One-Way Family of Functions
This page was built for publication: Natural proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906823)
