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

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/23255

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Atserias, Albert
dc.contributor.author	Müller, Moritz
dc.contributor.author	Oliva Valls, Sergi
dc.date	2013
dc.identifier.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.
dc.identifier.citation	978-076954997-2
dc.identifier.citation	10.1109/CCC.2013.20
dc.identifier.uri	http://hdl.handle.net/2117/23255
dc.language.iso	eng
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation	http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6597754
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Computational complexity
dc.subject	Lower bounds
dc.subject	Pigeonhole principle
dc.subject	Complexitat computacional
dc.title	Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.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.
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author