Loading...
Loading...

Go to the content (press return)

Lower bounds for DNF-refutations of a relativized weak pigeonhole principle

Author
Atserias, A.; Müller, M.; Oliva, S.
Type of activity
Presentation of work at congresses
Name of edition
28th IEEE Conference on Computational Complexity
Date of publication
2013
Presentation's date
2013-06-05
Book of congress proceedings
2013 IEEE Conference on Computational Complexity, CCC 2013: 5-7 June 2013 Palo Alto, California, USA: proceedings
First page
109
Last page
120
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
DOI
https://doi.org/10.1109/CCC.2013.20 Open in new window
Project funding
Métodos formales y algoritmos para el diseño de sistemas
TIN2010-20967-C04-04
Repository
http://hdl.handle.net/2117/23255 Open in new window
URL
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6597754 Open in new window
Abstract
The relativized weak pigeonhole principle states that if at least $2n$ out of $n2$ pigeons fly into $n$ holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size ${(\log n)^{3/2-\epsilon}}$ for every $\epsilon > 0$ and every sufficiently large~$n$. For its proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition. © 2013 IEEE. The relativized weak pigeo...
Citation
Atserias, A.; Müller, M.; Oliva, S. Lower bounds for DNF-refutations of a relativized weak pigeonhole principle. A: IEEE Conference on Computational Complexity. "2013 IEEE Conference on Computational Complexity, CCC 2013: 5-7 June 2013 Palo Alto, California, USA: proceedings". Palo Alto, California: Institute of Electrical and Electronics Engineers (IEEE), 2013, p. 109-120.
Keywords
Lower bounds, Pigeonhole principle
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Atserias, Albert  (author and speaker )
  • Müller, Moritz  (author and speaker )
  • Oliva Valls, Sergi  (author and speaker )

Attachments