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

DOI10.1017/JSL.2014.56zbMATH Open1386.03070OpenAlexW2105447726MaRDI QIDQ5501765FDOQ5501765

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

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

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)

Cites Work

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

Cited In (5)

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

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)