Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
From MaRDI portal
Publication:2255289
DOI10.4007/annals.2015.181.2.1zbMath1376.03055OpenAlexW2114400329MaRDI 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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (21)
Substitutions into propositional tautologies ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS ⋮ Circuit lower bounds in bounded arithmetics ⋮ Unnamed Item ⋮ Randomness buys depth for approximate counting ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ The treewidth of proofs ⋮ Unnamed Item ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Propositional proof complexity ⋮ Random resolution refutations ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Separation results for the size of constant-depth propositional proofs ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Reflections on Proof Complexity and Counting Principles
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
This page was built for publication: Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
