Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2605.10941 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910209580990464 |
|---|---|
| author | de Rezende, Susanna F. Engström, David Ghannane, Yassine Janett, Duri Andrea Riazanov, Artur |
| author_facet | de Rezende, Susanna F. Engström, David Ghannane, Yassine Janett, Duri Andrea Riazanov, Artur |
| contents | We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations of the binary encoding of clique formulas on randomly sampled dense graphs. Moreover, we show that the randomized communication complexity of finding a falsified clause in these formulas is polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10941 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity de Rezende, Susanna F. Engström, David Ghannane, Yassine Janett, Duri Andrea Riazanov, Artur Computational Complexity We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations of the binary encoding of clique formulas on randomly sampled dense graphs. Moreover, we show that the randomized communication complexity of finding a falsified clause in these formulas is polynomial. |
| title | Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.10941 |