𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dual weak pigeonhole principle, Boolean complexity, and derandomization

✍ Scribed by Emil Jeřábek

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
410 KB
Volume
129
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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