Large clique is hard on average for resolution
type: Item
instance of: scholarly article
title: Large clique is hard on average for resolution
DOI: 10.1007/978-3-030-79416-3_22
author: Shuo Pang
publication date: 2022-03-21T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7493542
zbMATH Keywords: resolution
zbMATH Keywords: \(k\)-clique
zbMATH Keywords: random graphs
zbMATH Keywords: regular resolution
MaRDI profile type: Publication
full work available at URL: 978-3-030-79416-3 22
OpenAlex ID: W3174911079
cites work: An exponential separation between regular and general resolution
cites work: Clique is hard on average for regular resolution
cites work: Automating Resolution is NP-Hard
cites work: The resolution complexity of independent sets and vertex covers in random graphs
cites work: Parameterized Complexity of DPLL Search Procedures
cites work: Cliques in random graphs
cites work: Strong ETH and resolution via games and the multiplicity of strategies
cites work: Monotone circuit lower bounds from resolution
cites work: Automating cutting planes is NP-hard
cites work: Communication Lower Bounds via Critical Block Sensitivity
cites work: The intractability of resolution
cites work: On the virtue of succinct proofs
cites work: The complexity of proving that a graph is Ramsey
cites work: Q3688439
cites work: Proofs as Games
cites work: Separation of the monotone NC hierarchy
cites work: Q3758729
cites work: Q4737899
cites work: Q5302097
cites work: Short resolution proofs for a sequence of tricky formulas
cites work: Efficient algorithms for clique problems
cites work: Simplified and improved separations between regular and general resolution by lifting
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
description: scientific article; zbMATH DE number 7493542