| Autor: |
Atserias, Albert, Bonacina, Ilario, de Rezende, Susanna F., Lauria, Massimo, Nordström, Jakob, Razborov, Alexander |
| Rok vydání: |
2020 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We prove that for $k \ll \sqrt[4]{n}$ regular resolution requires length $n^{\Omega(k)}$ to establish that an Erd\H{o}s-R\'enyi 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^{\Omega(k)}$ lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
