A new proof of the weak pigeonhole principle
From MaRDI portal
Publication:5895202
DOI10.1145/335305.335348zbMATH Open1296.03033OpenAlexW2095226356MaRDI QIDQ5895202FDOQ5895202
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
Recommendations
Cited In (19)
- On the complexity of resolution with bounded conjunctions
- A model-theoretic characterization of the weak pigeonhole principle
- Title not available (Why is that?)
- Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms
- Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
- Structures interpretable in models of bounded arithmetic
- The ordering principle in a fragment of approximate counting
- On Independence of Variants of the Weak Pigeonhole Principle
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- Propositional proof complexity
- A new proof of the weak pigeonhole principle
- On the weak pigeonhole principle
- Regular resolution lower bounds for the weak pigeonhole principle
- Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
- Title not available (Why is that?)
- Short proofs of the pigeonhole formulas based on the connection method
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- On the pigeonhole and related principles in deep inference and monotone systems
- The weak pigeonhole principle for function classes inS12
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)
