Clique is hard on average for regular resolution

DOI10.1145/3188745.3188856MaRDI QIDQ5230344zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordstrom, Alexander Razborov

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.09476

zbMATH Keywords

\(k\)-cliqueErdős-Renyi random graphsproof complexityregular resolution

Mathematics Subject Classification ID

Complexity of proofs (03F20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We prove that for $kllsqrt[4]n$ regular resolution requires length $n^{Omega(k)}$ to establish that an ErdH{o}s-R'enyi 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^{Omega(k)}$ lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

Recommendations

• Clique Is Hard on Average for Regular Resolution
• Large clique is hard on average for resolution
• Clique-width: when hard does not mean impossible
• On the clique-game
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• scientific article; zbMATH DE number 1670809
• Hardness and methods to solve CLIQUE
• On cliques and bicliques
• On cliques and bicliques
• Finding Large Clique Minors is Hard

Cited in

(12)

• Cliques enumeration and tree-like resolution proofs
• Large clique is hard on average for resolution
• Characterizing Tseitin-formulas with short regular resolution refutations
• Clique Is Hard on Average for Regular Resolution
• Resolution and the binary encoding of combinatorial principles
• scientific article; zbMATH DE number 7561756 (Why is no real title available?)
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Characterizing Tseitin-Formulas with Short Regular Resolution Refutations
• Proof complexity and the binary encoding of combinatorial principles
• Cryptography from planted graphs: security with logarithmic-size messages
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Proof complexity of modal resolution

This page was built for publication: Clique is hard on average for regular resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230344)