Large clique is hard on average for resolution
From MaRDI portal
Publication:2117104
DOI10.1007/978-3-030-79416-3_22OpenAlexW3174911079MaRDI QIDQ2117104
Publication date: 21 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_22
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for clique problems
- The intractability of resolution
- The complexity of proving that a graph is Ramsey
- Short resolution proofs for a sequence of tricky formulas
- Separation of the monotone NC hierarchy
- Strong ETH and resolution via games and the multiplicity of strategies
- The resolution complexity of independent sets and vertex covers in random graphs
- Simplified and improved separations between regular and general resolution by lifting
- Proofs as Games
- Linear degree extractors and the inapproximability of max clique and chromatic number
- An exponential separation between regular and general resolution
- Cliques in random graphs
- Communication Lower Bounds via Critical Block Sensitivity
- Automating Resolution is NP-Hard
- Automating cutting planes is NP-hard
- Clique is hard on average for regular resolution
- Monotone circuit lower bounds from resolution
- On the virtue of succinct proofs
- Parameterized Complexity of DPLL Search Procedures
This page was built for publication: Large clique is hard on average for resolution
