A new proof of the weak pigeonhole principle

DOI10.1145/335305.335348MaRDI QIDQ5895202zbMATH OpenOpenAlexFDO

Authors Alexis Maciel, Toniann Pitassi, Alan R. Woods

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335348

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• A new proof of the weak pigeonhole principle
• scientific article; zbMATH DE number 1223618
• On the weak pigeonhole principle
• Resolution lower bounds for the weak pigeonhole principle
• Exponential lower bounds for the pigeonhole principle

Cited in

(20)

• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
• A model-theoretic characterization of the weak pigeonhole principle
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• On the complexity of resolution with bounded conjunctions
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Structures interpretable in models of bounded arithmetic
• On the weak pigeonhole principle
• The ordering principle in a fragment of approximate counting
• The weak pigeonhole principle for function classes inS12
• On the pigeonhole and related principles in deep inference and monotone systems
• Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• scientific article; zbMATH DE number 1834646 (Why is no real title available?)
• Regular resolution lower bounds for the weak pigeonhole principle
• On Independence of Variants of the Weak Pigeonhole Principle
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• A new proof of the weak pigeonhole principle
• Propositional proof complexity
• Refuting perfect matchings in spectral expanders is hard
• Short proofs of the pigeonhole formulas based on the connection method

This page was built for publication: A new proof of the weak pigeonhole principle

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