Clique is hard on average for regular resolution

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/123124

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Atserias, Albert
dc.contributor.author	Bonacina, Ilario
dc.contributor.author	Rezende, Susanna F. de
dc.contributor.author	Lauria, Massimo
dc.contributor.author	Nordström, Jakob
dc.contributor.author	Razborov, Alexander
dc.date	2018
dc.identifier.citation	Atserias, A., Bonacina, I., Rezende, S., Lauria, M., Nordström, J., Razborov, A. Clique is hard on average for regular resolution. A: ACM Symposium on Theory of Computing. "Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing". New York: Association for Computing Machinery (ACM), 2018, p. 866-877.
dc.identifier.citation	978-1-4503-5559-9
dc.identifier.citation	10.1145/3188745.3188856
dc.identifier.uri	http://hdl.handle.net/2117/123124
dc.language.iso	eng
dc.publisher	Association for Computing Machinery (ACM)
dc.relation	https://dl.acm.org/citation.cfm?doid=3188745.3188856
dc.relation	info:eu-repo/grantAgreement/EC/H2020-648276-AUTAR
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Computational complexity
dc.subject	Algorithms
dc.subject	Proof complexity
dc.subject	Regular resolution
dc.subject	k-clique
dc.subject	Erdos-Rényi random graphs
dc.subject	Complexitat computacional
dc.subject	Algorismes
dc.title	Clique is hard on average for regular resolution
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.abstract	We prove that for k ≪4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
dc.description.abstract	Peer Reviewed

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Narrow proofs may be maximally long

Atserias, Albert; Lauria, Massimo; Nordström, Jakob

Narrow proofs may be maximally long

Atserias, Albert; Lauria, Massimo; Nordström, Jakob

Trade-offs between time and memory in a tighter model of CDCL SAT solvers

Elffers, J.; Johannsen, Jan; Lauria, Massimo; Magnard, Thomas; Nordström, Jakob; Vinyals, Marc

Circular (yet sound) proofs

Atserias, Albert; Lauria, Massimo

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

Atserias, Albert; Müller, Moritz; Oliva Valls, Sergi

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio