Clique Is Hard on Average for Regular Resolution

Autor: Susanna F. de Rezende, Ilario Bonacina, Jakob Nordström, Massimo Lauria, Albert Atserias, Alexander A. Razborov
Přispěvatelé: Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Jazyk: angličtina
Rok vydání: 2020
Předmět:
FOS: Computer and information sciences
Edge density
Clique
Erdos-Rényi random graphs
Algorismes
0102 computer and information sciences
Average complexity
Computational Complexity (cs.CC)
Clique (graph theory)
01 natural sciences
Upper and lower bounds
Combinatorics
Artificial Intelligence
k-clique
Multiplicative constant
0101 mathematics
Complexitat computacional
Mathematics
Random graphs
Regular resolution
Proof complexity
Grafs
Teoria de
010102 general mathematics
Resolution (electron density)
Graph
Running time
Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat [Àrees temàtiques de la UPC]
Computational complexity
Computer Science - Computational Complexity
010201 computation theory & mathematics
Hardware and Architecture
Control and Systems Engineering
Exponent
Graph (abstract data type)
Resolution
Software
Algorithms
Information Systems
Zdroj: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
Popis: 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. The first, second, and fourth authors were supported by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme/ERC grant agreement no. 648276 AUTAR. The third and fifth authors were supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ ERC grant agreement no. 279611 as well as by Swedish Research Council grants 621-2012-5645 and 2016-00782, and the second author did part of this work while at KTH Royal Institute of Technology supported by the same grants. The last author was supported by the Russian Foundation for Basic Research.
Databáze: OpenAIRE
Externí odkaz: