A new proof of the weak pigeonhole principle
From MaRDI portal
Publication:5894824
DOI10.1006/jcss.2002.1830zbMath1051.03049OpenAlexW4213091458MaRDI QIDQ5894824
Alexis Maciel, Toniann Pitassi, Alan R. Woods
Publication date: 12 September 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2002.1830
Related Items (23)
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ NP search problems in low fragments of bounded arithmetic ⋮ Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ Circuit principles and weak pigeonhole variants ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ The polynomial and linear hierarchies in models where the weak pigeonhole principle fails ⋮ A note on propositional proof complexity of some Ramsey-type statements ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ Approximate counting in bounded arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ The treewidth of proofs ⋮ The Complexity of Propositional Proofs ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Separation results for the size of constant-depth propositional proofs ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle
Cites Work
- Exponential lower bounds for the pigeonhole principle
- Resolution proofs of generalized pigeonhole principles
- Combinatorial principles in elementary number theory
- Polynomial size proofs of the propositional pigeonhole principle
- On models of arithmetic having non-modular substructure lattices
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Lower bounds to the size of constant-depth propositional proofs
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Regular resolution lower bounds for the weak pigeonhole principle
- Natural proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A new proof of the weak pigeonhole principle
