Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
From MaRDI portal
Publication:2255289
DOI10.4007/annals.2015.181.2.1zbMath1376.03055MaRDI QIDQ2255289
Publication date: 9 February 2015
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4007/annals.2015.181.2.1
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Characterizing Propositional Proofs as Noncommutative Formulas, INCOMPLETENESS IN THE FINITE DOMAIN, Unnamed Item, Reflections on Proof Complexity and Counting Principles, LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE, Circuit lower bounds in bounded arithmetics, Randomness buys depth for approximate counting, Substitutions into propositional tautologies, Feasibly constructive proofs of succinct weak circuit lower bounds, The treewidth of proofs, Random resolution refutations, Hardness assumptions in the foundations of theoretical computer science, Separation results for the size of constant-depth propositional proofs, A Framework for Space Complexity in Algebraic Proof Systems, On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution, On the correspondence between arithmetic theories and propositional proof systems – a survey
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular resolution lower bounds for the weak pigeonhole principle
- Random CNF's are hard for the polynomial calculus
- Lower bounds for the polynomial calculus
- Hardness vs randomness
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Resolution lower bounds for perfect matching principles
- An exponential separation between the parity principle and the pigeonhole principle
- Tautologies from Pseudo-Random Generators
- On the weak pigeonhole principle
- Candidate One-Way Functions Based on Expander Graphs
- Space Complexity in Propositional Calculus
- Randomness conductors and constant-degree lossless expanders
- Poisson approximation for large deviations
- CREW PRAM<scp>s</scp> and Decision Trees
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- On Interpolation and Automatization for Frege Systems
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Pseudorandom Generators in Propositional Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- The Complexity of Propositional Proofs
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Quantum lower bounds by polynomials
- Natural proofs
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
