Clique Is Hard on Average for Regular Resolution

DOI10.1145/3449352zbMath1499.68129OpenAlexW3173380426WikidataQ118123547 ScholiaQ118123547MaRDI QIDQ5056413

Jakob Nordström, Massimo Lauria, Susanna F. de Rezende, Albert Atserias, Ilario Bonacina, Alexander A. Razborov

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3449352

zbMATH Keywords

cliqueresolutionaverage complexity

Mathematics Subject Classification ID

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

Related Items (1)

Propositional proof complexity

This page was built for publication: Clique Is Hard on Average for Regular Resolution