Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
Susanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov · 2026
Read Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity by Susanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10941.txt.
Description
Susanna F. de Rezende and four colleagues prove average-case hardness for binary-encoded clique problems in proof and communication complexity. They prove clique formulas on random dense graphs need long cutting-planes proofs and long bounded-depth resolution-over-parities proofs.
At the same time, finding a falsified clause in those formulas stays cheap in randomized communication terms, separating proof length from communication cost. Clique problems anchor classical hardness theory, and unconditional super-polynomial lower bounds for clique itself would settle P versus NP, so average-case proof hardness is valuable evidence. Complexity theorists get a sharp average-case result in two models at once.
Catalog record
| CREATOR | Susanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88054 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10941