LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
From MaRDI portal
Publication:5501765
DOI10.1017/jsl.2014.56zbMath1386.03070OpenAlexW2105447726MaRDI QIDQ5501765
Albert Atserias, Moritz Müller, Sergi Oliva
Publication date: 14 August 2015
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2117/28085
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (3)
Narrow Proofs May Be Maximally Long ⋮ Relativization makes contradictions harder for resolution ⋮ Tight size-degree bounds for sums-of-squares proofs
Cites Work
- Unnamed Item
- Unnamed Item
- On approximate majority and probabilistic time
- Exponential lower bounds for the pigeonhole principle
- Combinatorics of first order structures and propositional proof systems
- Theoretical computer science. Petri nets.
- The intractability of resolution
- Special issue: Mathematical foundations of computer science. Selected papers from the 26th international symposium on mathematical foundations of computer science (MFCS 2001), Mariánské Lázně, Czech Republic, August 27-31, 2001
- A complexity gap for tree resolution
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- On uniformity within \(NC^ 1\)
- Proofs as Games
- On the weak pigeonhole principle
- A Remark on Stirling's Formula
- Short proofs are narrow—resolution made simple
- Space complexity of random formulae in resolution
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- The Complexity of Propositional Proofs
- Resolution lower bounds for the weak pigeonhole principle
- On sufficient conditions for unsatisfiability of random formulas
- A new proof of the weak pigeonhole principle
This page was built for publication: LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
