Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.10941 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |