Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Atserias, A.; Müller, M.; Oliva, S.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
28th IEEE Conference on Computational Complexity
Any de l'edició
2013
Data de presentació
2013-06-05
Llibre d'actes
2013 IEEE Conference on Computational Complexity, CCC 2013: 5-7 June 2013 Palo Alto, California, USA: proceedings
Pàgina inicial
109
Pàgina final
120
Editor
Institute of Electrical and Electronics Engineers (IEEE)
DOI
https://doi.org/10.1109/CCC.2013.20 Obrir en finestra nova
Projecte finançador
Métodos formales y algoritmos para el diseño de sistemas
TIN2010-20967-C04-04
Repositori
http://hdl.handle.net/2117/23255 Obrir en finestra nova
URL
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6597754 Obrir en finestra nova
Resum
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...
Citació
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.
Paraules clau
Lower bounds, Pigeonhole principle
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Atserias, Albert  (autor ponent)
  • Müller, Moritz  (autor ponent)
  • Oliva Valls, Sergi  (autor ponent)

Arxius