Lower bounds for DNF-refutations of a relativized weak pigeonhole principle

DOI10.1017/JSL.2014.56MaRDI QIDQ5501765zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Moritz Müller, Sergi Oliva

Publication date 14 August 2015

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/28085

zbMATH Keywords

approximate countingbounded arithmeticproof complexitybounded-depth Fregeweak pigeonhole principles

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Recommendations

• Resolution lower bounds for the weak functional pigeonhole principle.
• Resolution lower bounds for the weak pigeonhole principle
• A new proof of the weak pigeonhole principle
• On the weak pigeonhole principle
• Regular resolution lower bounds for the weak pigeonhole principle

Cites work

• scientific article; zbMATH DE number 486435 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• A Remark on Stirling's Formula
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• A complexity gap for tree resolution
• A new proof of the weak pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Combinatorics of first order structures and propositional proof systems
• Exponential lower bounds for the pigeonhole principle
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• On approximate majority and probabilistic time
• On sufficient conditions for unsatisfiability of random formulas
• On the weak pigeonhole principle
• On uniformity within \(NC^ 1\)
• Proofs as Games
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Resolution lower bounds for the weak pigeonhole principle
• Short proofs are narrow—resolution made simple
• Space complexity of random formulae in 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
• The Complexity of Propositional Proofs
• The intractability of resolution
• Theoretical computer science. Petri nets.

Cited in

(5)

• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
• Relativization makes contradictions harder for resolution
• Proof complexity and the binary encoding of combinatorial principles
• Tight size-degree bounds for sums-of-squares proofs
• Narrow proofs may be maximally long

This page was built for publication: Lower bounds for DNF-refutations of a relativized weak pigeonhole principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501765)