Large clique is hard on average for resolution

DOI10.1007/978-3-030-79416-3_22MaRDI QIDQ2117104zbMATH OpenOpenAlexFDO

Authors Shuo Pang

Publication date 21 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-79416-3_22

zbMATH Keywords

\(k\)-cliquerandom graphsregular resolutionresolution

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• An exponential separation between regular and general resolution
• Automating cutting planes is NP-hard
• Automating resolution is NP-hard
• Clique is hard on average for regular resolution
• Cliques in random graphs
• Communication lower bounds via critical block sensitivity
• Efficient algorithms for clique problems
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 2087215 (Why is no real title available?)
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Monotone circuit lower bounds from resolution
• On the virtue of succinct proofs
• Parameterized Complexity of DPLL Search Procedures
• Proofs as Games
• Separation of the monotone NC hierarchy
• Short resolution proofs for a sequence of tricky formulas
• Simplified and improved separations between regular and general resolution by lifting
• Strong ETH and resolution via games and the multiplicity of strategies
• The intractability of resolution
• The resolution complexity of independent sets and vertex covers in random graphs

Cited in

(4)

• Clique is hard on average for regular resolution
• 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
• Very large cliques are easy to detect

This page was built for publication: Large clique is hard on average for resolution

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