We prove that for k ≪4n 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.

Clique is hard on average for regular resolution / Atserias, Albert; Lauria, Massimo; Bonacina, Ilario; Nordström, Jakob; De Rezende, Susanna F; Razborov, Alexander. - (2018), pp. 646-659. (Intervento presentato al convegno 50th Annual ACM Symposium on Theory of Computing, STOC 2018 tenutosi a usa) [10.1145/3188745.3188856].

Clique is hard on average for regular resolution

Lauria, Massimo;Bonacina, Ilario;
2018

Abstract

We prove that for k ≪4n 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.
2018
50th Annual ACM Symposium on Theory of Computing, STOC 2018
Erdős-Rényi random graphs; K-clique; Proof complexity; Regular resolution; Software
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Clique is hard on average for regular resolution / Atserias, Albert; Lauria, Massimo; Bonacina, Ilario; Nordström, Jakob; De Rezende, Susanna F; Razborov, Alexander. - (2018), pp. 646-659. (Intervento presentato al convegno 50th Annual ACM Symposium on Theory of Computing, STOC 2018 tenutosi a usa) [10.1145/3188745.3188856].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1199263
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 11
social impact