Clique is hard on average for regular resolution
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
We prove that for k ≪ 4 n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
Original language | English |
---|---|
Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |
Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |
Number of pages | 14 |
Publisher | ACM Association for Computing Machinery |
Publication date | 20 Jun 2018 |
Pages | 646-659 |
ISBN (Electronic) | 9781450355599 |
DOIs | |
Publication status | Published - 20 Jun 2018 |
Externally published | Yes |
Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 |
Conference
Conference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|
Land | United States |
By | Los Angeles |
Periode | 25/06/2018 → 29/06/2018 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
Series | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|
ISSN | 0737-8017 |
- Erdős-Rényi random graphs, K-clique, Proof complexity, Regular resolution
Research areas
ID: 251867616