Clique is hard on average for regular resolution

DOI10.1145/3188745.3188856zbMath1427.68102arXiv2012.09476OpenAlexW2809359463MaRDI QIDQ5230344

Albert Atserias, Ilario Bonacina, Jakob Nordström, Massimo Lauria, Susanna F. de Rezende, Alexander A. 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

proof complexity\(k\)-cliqueregular resolutionErdős-Renyi random graphs

Mathematics Subject Classification ID

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

Related Items (8)

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Proof complexity of modal resolution ⋮ Cliques enumeration and tree-like resolution proofs ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Unnamed Item ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Large clique is hard on average for resolution ⋮ Characterizing Tseitin-formulas with short regular resolution refutations

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