๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Lower Bounds for Randomized Consensus under a Weak Adversary

โœ Scribed by Attiya, Hagit; Censor-Hillel, Keren

Book ID
118181084
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
277 KB
Volume
39
Category
Article
ISSN
0097-5397

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.