Clique is hard on average for regular resolution

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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.

Detaljer

Författare
  • Albert Atserias
  • Ilario Bonacina
  • Susanna F. De Rezende
  • Massimo Lauria
  • Jakob Nordström
  • Alexander Razborov
Externa organisationer
  • Polytechnic University of Catalonia
  • Sapienza University of Rome
  • KTH Royal Institute of Technology
  • University of Chicago
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Titel på värdpublikationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
RedaktörerMonika Henzinger, David Kempe, Ilias Diakonikolas
FörlagAssociation for Computing Machinery (ACM)
Sidor646-659
Antal sidor14
ISBN (elektroniskt)9781450355599
StatusPublished - 2018 jun 20
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, USA
Varaktighet: 2018 jun 252018 jun 29

Publikationsserier

NamnProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (tryckt)0737-8017

Konferens

Konferens50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandUSA
OrtLos Angeles
Period2018/06/252018/06/29