2026-09-08T01:21:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26540 2026-09-05T19:47:10Z ddc:004 open_access

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 proof complexity communication complexity cutting planes bounded-depth resolution over parities clique problem average-case hardness binary encoding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanna F. de Rezende and David Engström and Yassine Ghannane and Duri Andrea Janett and Artur Riazanov 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.151 urn:nbn:de:0030-drops-265407 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.151 eng https://creativecommons.org/licenses/by/4.0/legalcode