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