𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle

✍ Scribed by Toniann Pitassi*; Ran Raz†

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
275 KB
Volume
24
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Resolution lower bounds for the weak fun
Resolution lower bounds for the weak functional pigeonhole principle
✍ Alexander A. Razborov 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 243 KB

We show that every resolution proof of the functional version FPHP m n of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp( (n=(log m) 2 )). This implies an exp( (n 1=3 )) bound when the number of pigeons m is arbitrary.

The weak pigeonhole principle for functi
The weak pigeonhole principle for function classes in S12
✍ Norman Danner; Chris Pollett 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB 👁 1 views

## Abstract It is well known that __S__ ^1^~2~ cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in __S__ ^1^~2~ for provably weaker function class

Improved bounds on the Weak Pigeonhole P
Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms
✍ Albert Atserias 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 158 KB

We show that the known bounded-depth proofs of the Weak Pigeonhole Principle PHP 2n n in size n O(log(n)) are not optimal in terms of size. More precisely, we give a size-depth trade-o upper bound: there are proofs of size n O(d(log(n)) 2=d ) and depth O(d). This solves an open problem of Maciel et