Clique Is Hard on Average for Regular Resolution

DOI10.1145/3449352MaRDI QIDQ5056413zbMATH OpenOpenAlexWikidataFDO

Authors Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordstrom, Alexander 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

average complexitycliqueresolution

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms (68W40)

Recommendations

• Clique is hard on average for regular resolution
• Cliques enumeration and tree-like resolution proofs
• The monotone complexity of \(k\)-clique on random graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The resolution complexity of independent sets and vertex covers in random graphs

Cited in

(5)

• Cliques enumeration and tree-like resolution proofs
• Clique is hard on average for regular resolution
• Propositional proof complexity
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs

Describes a project that uses

Uses Software

• SageMath

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 Q5056413)