|
Título:
|
Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
|
|
Autor/a:
|
Atserias, Albert; Müller, Moritz; Oliva Valls, Sergi
|
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
|
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 2((log n)3/2-ϵ) for every ε > 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. |
|
Abstract:
|
Peer Reviewed |
|
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
-Computational complexity
-Lower bounds
-Pigeonhole principle
-Complexitat computacional |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Objeto de conferencia |
|
Editor:
|
Institute of Electrical and Electronics Engineers (IEEE)
|
|
Compartir:
|
|
