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

CREATORSusanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88054
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.10941

Browse the full library · About the Tower of Babel