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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
