arxiv: 2605.10941 · v1 · submitted 2026-05-11 · 💻 cs.CC

Recognition: no theorem link

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity

Susanna F. de Rezende , David Engstr\"om , Yassine Ghannane , Duri Andrea Janett , Artur Riazanov

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:13 UTC · model grok-4.3

classification 💻 cs.CC

keywords average-case hardnessclique formulascutting planesresolution over paritiesbinary encodingproof complexitycommunication complexityrandom graphs

0 comments

The pith

The binary encoding of clique on random dense graphs requires exponential-length refutations in cutting planes and bounded-depth resolution over parities, while randomized communication complexity for finding a falsified clause stays only a

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies average-case hardness for proving the absence of large cliques in graphs. It focuses on the binary encoding of clique formulas and examines them on randomly sampled dense graphs. Exponential lower bounds are established for the length of refutations in cutting planes and bounded-depth resolution over parities. In contrast, the randomized communication complexity of finding a falsified clause in these formulas is shown to be polynomial. This establishes a separation between proof length and communication cost under the average-case distribution.

Core claim

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.

What carries the argument

The binary encoding of clique formulas on randomly sampled dense graphs, which supports exponential lower bounds on refutation length in cutting planes and bounded-depth resolution over parities while admitting only polynomial randomized communication complexity for locating a falsified clause.

If this is right

Refuting the non-existence of large cliques in random dense graphs demands exponential effort in these proof systems under the binary encoding.
Finding a falsified clause can be accomplished with polynomial randomized communication despite the long proofs.
The average-case hardness for clique extends specifically to these refutation systems on the chosen random graph model.
Proof complexity measures and communication complexity can diverge on the same set of instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The separation may extend to other combinatorial search problems if encoded in a similar binary fashion.
Different graph distributions or encodings could be tested to see whether the polynomial communication bound persists.
This average-case result might inform constructions where proof systems are compared directly to interactive protocols.

Load-bearing premise

The specific binary encoding of the clique formulas and the distribution of randomly sampled dense graphs must produce instances that are representative of the average-case hardness.

What would settle it

Discovery of a polynomial-length refutation in cutting planes or bounded-depth resolution over parities for the binary-encoded clique formulas on a random dense graph would falsify the exponential lower bound.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The abstract claims exponential lower bounds for cutting planes and bounded-depth Res(⊕) on binary-encoded clique formulas over random dense graphs, plus a polynomial randomized communication bound for finding falsified clauses.

read the letter

The main thing here is the claimed exponential lower bounds for cutting planes and bounded-depth resolution over parities on the binary encoding of clique formulas for randomly sampled dense graphs, together with a polynomial randomized communication complexity for finding a falsified clause. This pairing of proof hardness with communication ease is the core result on offer. It looks new in the specific mix of binary encoding, average-case random dense graphs, and these two proof systems. Most prior clique lower bounds in proof complexity have been worst-case or used different encodings, so the average-case angle stands out from the abstract. The paper does well by delivering both a lower bound in the proof systems and an upper bound in communication for the same formulas. That contrast can help map relative hardness across models without needing to invent new problems. The soft spots are straightforward and tied to what we have. Only the abstract is available, so the precise definition of the binary encoding, the exact random graph distribution, and the actual proofs cannot be checked. If the encoding turns out to add unintended structure or if the random model has special properties that simplify the argument, the exponential bounds could be narrower than they first appear. Soundness is not verifiable yet. This is for specialists in proof complexity and communication complexity who track average-case hardness for canonical NP problems. A reader in that niche would find the contrast useful even if the impact stays contained. It deserves serious peer review once the full paper is available. The claims are specific enough that referees can test the encoding, the random model, and the derivations directly.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to establish exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations for the binary encoding of clique formulas on randomly sampled dense graphs, and to show that the randomized communication complexity of finding a falsified clause in these formulas is polynomial.

Significance. If substantiated, these results would advance the study of average-case hardness in proof complexity by connecting a canonical combinatorial problem (clique) under a specific encoding and random-graph distribution to lower bounds in cutting planes and parity resolution. The polynomial communication complexity bound would additionally strengthen links between proof systems and communication protocols for search problems.

major comments (1)

[Abstract] Abstract: The exponential lower bounds and polynomial communication complexity are asserted without any definitions of the binary encoding, the random dense graph distribution, or proof outlines. This prevents verification of whether the claims follow from the stated models or contain hidden dependencies on the encoding choices.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report and the opportunity to clarify our presentation. We address the single major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: The exponential lower bounds and polynomial communication complexity are asserted without any definitions of the binary encoding, the random dense graph distribution, or proof outlines. This prevents verification of whether the claims follow from the stated models or contain hidden dependencies on the encoding choices.

Authors: The abstract is deliberately concise, as is standard, to summarize the main contributions without exceeding typical length constraints. Full definitions appear in the body of the manuscript: the binary encoding of the clique formula is introduced in Section 2, where each potential edge is represented by a binary variable and the formula encodes the absence of a clique of size k via appropriate clauses. The random dense graph distribution is the Erdős–Rényi model G(n,p) with constant p (specifically p=1/2 in our main theorems), defined and analyzed in Section 3 together with the relevant concentration properties. Proof outlines for the cutting-planes and Res(⊕) lower bounds are given in the introduction and developed in Sections 4 and 5 using the random-graph structure to obtain average-case hardness via a suitable potential function and width-reduction arguments. The polynomial randomized communication complexity for the falsified-clause search problem is established in Section 6 by exhibiting an explicit protocol whose communication cost is O(log n). These sections contain no hidden dependencies; the encoding is chosen precisely because it is the natural one that aligns with communication-complexity lower-bound techniques. Consequently the abstract does not impede verification once the full manuscript is consulted. revision: no

Circularity Check

0 steps flagged

No circularity detectable from abstract

full rationale

Only the abstract is available, which states exponential lower bounds for cutting planes and bounded-depth resolution over parities refutations of binary-encoded clique formulas on random dense graphs, plus polynomial randomized communication complexity for finding falsified clauses. No equations, derivations, fitted parameters, or self-citations are exhibited that could reduce the claimed results to their inputs by construction. The results are presented as following from standard combinatorial and information-theoretic arguments on the specific encoding and distribution, without any load-bearing step that collapses to self-definition or renaming. This matches the default expectation for non-circular papers in proof complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the full ledger cannot be audited. The claims rest on standard propositional logic, graph theory, and proof-complexity techniques for lower bounds.

axioms (1)

standard math Standard axioms of propositional logic and basic graph theory
Used to define clique formulas, refutations, and random dense graphs.

pith-pipeline@v0.9.0 · 5344 in / 1342 out tokens · 53920 ms · 2026-05-12T03:13:50.021106+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

[1]

Quantum communication advantage in TFNP

Yaroslav Alekseev and Dmitry Itsykson. Lifting to bounded-depth and regular resolutions over parities via games. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC ’25), pages 584–595, 2025.doi:10.1145/3717823.3718150

work page doi:10.1145/3717823.3718150 2025
[2]

de Rezende, Massimo Lauria, Jakob Nordstr¨ om, and Alexander Razborov

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordstr¨ om, and Alexander Razborov. Clique is hard on average for regular resolution.Journal of the ACM, 68(4):23:1–23:26, 2021. Preliminary version inSTOC ’18.doi:10.1145/3449352

work page doi:10.1145/3449352 2021
[3]

The resolution complexity of inde- pendent sets and vertex covers in random graphs.Computational Complexity, 16(3):245–297,

Paul Beame, Russell Impagliazzo, and Ashish Sabharwal. The resolution complexity of inde- pendent sets and vertex covers in random graphs.Computational Complexity, 16(3):245–297,

work page
[4]

Preliminary version inCCC ’01.doi:10.1007/S00037-007-0230-0

work page doi:10.1007/s00037-007-0230-0
[5]

Towards understanding and harnessing the potential of clause learning.Journal of Artificial Intelligence Research, 22(1):319–351, 2004

Paul Beame, Henry Kautz, and Ashish Sabharwal. Towards understanding and harnessing the potential of clause learning.Journal of Artificial Intelligence Research, 22(1):319–351, 2004. doi:10.1613/jair.1410

work page doi:10.1613/jair.1410 2004
[6]

Lower bounds for Lov´ asz–Schrijver systems and beyond follow from multiparty communication complexity.SIAM Journal on Computing, 37(3):845–869, 2007

Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for Lov´ asz–Schrijver systems and beyond follow from multiparty communication complexity.SIAM Journal on Computing, 37(3):845–869, 2007. Preliminary version inICALP ’05.doi:10.1137/060654645

work page doi:10.1137/060654645 2007
[7]

Multiparty communication complexity of collision- finding and cutting planes proofs of concise pigeonhole principles

Paul Beame and Michael Whitmeyer. Multiparty communication complexity of collision- finding and cutting planes proofs of concise pigeonhole principles. InProcceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP ’25), volume 334 ofLIPIcs, pages 21:1–21:20, 2025.doi:10.4230/LIPIcs.ICALP.2025.21

work page doi:10.4230/lipics.icalp.2025.21 2025
[8]

Parameterized complexity of DPLL search procedures.ACM Transactions on Computational Logic, 14(3):20:1–20:21, 2013

Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. Parameterized complexity of DPLL search procedures.ACM Transactions on Computational Logic, 14(3):20:1–20:21, 2013. Pre- liminary version inSAT ’11.doi:10.1145/2499937.2499941

work page doi:10.1145/2499937.2499941 2013
[9]

Parameterized bounded-depth Frege is not optimal.ACM Transactions on Computation Theory (TOCT), 4(3):1–16, 2012

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, and Alexander A Razborov. Parameterized bounded-depth Frege is not optimal.ACM Transactions on Computation Theory (TOCT), 4(3):1–16, 2012. Preliminary version inICALP ’11.doi:10.1145/2355580.2355582

work page doi:10.1145/2355580.2355582 2012
[10]

Exponential lower bounds on the size of reslin proofs of nearly quadratic depth.arXiv preprint arXiv:2507.23008, 2025

Sreejata Kishor Bhattacharya and Arkadev Chattopadhyay. Exponential lower bounds on the size of reslin proofs of nearly quadratic depth.arXiv preprint arXiv:2507.23008, 2025. doi:10.48550/ARXIV.2507.23008

work page doi:10.48550/arxiv.2507.23008 2025
[12]

Buss and Jakob Nordstr¨ om

Sam R. Buss and Jakob Nordstr¨ om. Proof complexity and SAT solving. In Armin Biere, Marijn J. H. Heule, Hans van Maaren, and Toby Walsh, editors,Handbook of Satisfiability, volume 336 ofFrontiers in Artificial Intelligence and Applications, chapter 7, pages 233–350. IOS Press, 2nd edition, 2021.doi:10.3233/faia200990. 28

work page doi:10.3233/faia200990 2021
[13]

Lower bounds for bit pigeonhole principles in bounded-depth resolution over parities.arXiv preprint arXiv:2511.20023, 2025.doi:10

Farzan Byramji and Russell Impagliazzo. Lower bounds for bit pigeonhole principles in bounded-depth resolution over parities.arXiv preprint arXiv:2511.20023, 2025.doi:10. 48550/ARXIV.2511.20023

work page arXiv 2025
[14]

Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider

Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. InProceedings of the 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS ’16), page 261–270, 2016.doi:10.1145/2840728. 2840746

work page doi:10.1145/2840728 2016
[15]

Equality alone does not simulate randomness

Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. InProceedings of the 34th Computational Complexity Conference (CCC ’19), pages 14:1–14:11, 2019.doi:10.4230/LIPIcs.CCC.2019.14

work page doi:10.4230/lipics.ccc.2019.14 2019
[16]

Kanj, and Ge Xia

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Linear FPT reductions and com- putational lower bounds. InProceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC ’04), pages 212–221, 2004.doi:10.1145/1007352.1007391

work page doi:10.1145/1007352.1007391 2004
[17]

A lower bound on the trace norm of boolean matrices and its applications

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. A lower bound on the trace norm of boolean matrices and its applications. In Proceedings of the 16th Innovations in Theoretical Computer Science Conference (ITCS ’25), pages 37:1–37:15, 2025.doi:10.4230/LIPIcs.ITCS.2025.37

work page doi:10.4230/lipics.itcs.2025.37 2025
[18]

Using the Groebner basis algo- rithm to find proofs of unsatisfiability

Matthew Clegg, Jeffery Edmonds, and Russell Impagliazzo. Using the Groebner basis algo- rithm to find proofs of unsatisfiability. InProceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), page 174–183, 1996.doi:10.1145/237814.237860

work page doi:10.1145/237814.237860 1996
[19]

On the complexity of cutting- plane proofs.Discrete Applied Mathematics, 18(1):25–38, 1987.doi:10.1016/0166-218x(87) 90039-4

William Cook, Collette Rene Coullard, and Gy¨ orgy Tur´ an. On the complexity of cutting- plane proofs.Discrete Applied Mathematics, 18(1):25–38, 1987.doi:10.1016/0166-218x(87) 90039-4

work page doi:10.1016/0166-218x(87 1987
[20]

Proof complexity and the binary encoding of combinatorial principles.SIAM Journal on Computing, 53(3):764–802, 2024.doi:10.1137/20M134784X

Stefan Dantchev, Nicola Galesi, Abdul Ghani, and Barnaby Martin. Proof complexity and the binary encoding of combinatorial principles.SIAM Journal on Computing, 53(3):764–802, 2024.doi:10.1137/20M134784X

work page doi:10.1137/20m134784x 2024
[21]

and Li, Jerry and Liu, Allen and Narayanan, Shyam , booktitle =

Susanna de Rezende, Aaron Potechin, and Kilian Risse. Clique is hard on average for unary Sherali-Adams. InProceedings of the 64th IEEE Annual Symposium on Foundations of Com- puter Science (FOCS 23’), pages 12–25, 2023.doi:10.1109/focs57990.2023.00008

work page doi:10.1109/focs57990.2023.00008 2023
[22]

Lower bounds for regular resolution over parities

Klim Efremenko, Michal Garl´ ık, and Dmitry Itsykson. Lower bounds for regular resolution over parities. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), pages 640–651, 2024.doi:10.1145/3618260.3649652

work page doi:10.1145/3618260.3649652 2024
[23]

Amortized closure and its applications in lifting for resolution over parities

Klim Efremenko and Dmitry Itsykson. Amortized closure and its applications in lifting for resolution over parities. InProceedings of the 40th Computational Complexity Conference (CCC ’25), pages 8:1–8:24, 2025.doi:10.4230/LIPICS.CCC.2025.8

work page doi:10.4230/lipics.ccc.2025.8 2025
[24]

Monotone circuit lower bounds from resolution.Theory of Computing, 16(13):1–30, 2020

Ankit Garg, Mika G¨ o¨ os, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution.Theory of Computing, 16(13):1–30, 2020. Preliminary version inSTOC ’18. doi:10.4086/TOC.2020.V016A013. 29

work page doi:10.4086/toc.2020.v016a013 2020
[25]

Quantum communication advantage in TFNP

Mika G¨ o¨ os, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in TFNP. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, (STOC ’25), pages 1465–1475, 2025.doi:10.1145/3717823.3718155

work page doi:10.1145/3717823.3718155 2025
[26]

Arya and D

Mika G¨ o¨ os, Nathaniel Harms, and Artur Riazanov. Equality is far weaker than constant-cost communication. InProceedings of the 29th International Conference on Randomization and Computation (RANDOM ’25), volume 353, pages 58:1–58:14, 2025.doi:10.4230/LIPIcs. APPROX/RANDOM.2025.58

work page doi:10.4230/lipics 2025
[27]

Query-to-communication lifting for BPP.SIAM Journal on Computing, 49(4):FOCS17–441–FOCS17–461, 2020.doi:10.1137/ 17M115339X

Mika G¨ o¨ os, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP.SIAM Journal on Computing, 49(4):FOCS17–441–FOCS17–461, 2020.doi:10.1137/ 17M115339X

work page 2020
[28]

Communication lower bounds via critical block sensitivity

Mika G¨ o¨ os and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47(5):1778–1806, 2018. Preliminary version inSTOC ’14.doi: 10.1137/16M1082007

work page doi:10.1137/16m1082007 2018
[29]

Armin Haken and Stephen A. Cook. An exponential lower bound for the size of monotone real circuits.Journal of Computer and System Sciences, 58(2):326–335, 1999.doi:10.1006/ jcss.1998.1617

work page arXiv 1999
[30]

Clique is hard to approximate withinn 1−ε.Acta Mathematica, 182(1), 1999

Johan H˚ astad. Clique is hard to approximate withinn 1−ε.Acta Mathematica, 182(1), 1999. doi:DOI:10.1007/BF02392825

work page doi:10.1007/bf02392825 1999
[31]

A note on monotone real circuits.Information Processing Letters, 131:15–19, 2018.doi:10.1016/j.ipl.2017.11.002

Pavel Hrubeˇ s and Pavel Pudl´ ak. A note on monotone real circuits.Information Processing Letters, 131:15–19, 2018.doi:10.1016/j.ipl.2017.11.002

work page doi:10.1016/j.ipl.2017.11.002 2018
[32]

On the virtue of succinct proofs: amplifying commu- nication complexity hardness to time-space trade-offs in proof complexity

Trinh Huynh and Jakob Nordstr¨ om. On the virtue of succinct proofs: amplifying commu- nication complexity hardness to time-space trade-offs in proof complexity. InProceedings of the 44th Symposium on Theory of Computing Conference, (STOC ’12), pages 233–248, 2012. doi:10.1145/2213977.2214000

work page doi:10.1145/2213977.2214000 2012
[33]

Upper and lower bounds for tree- like cutting planes proofs

Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower bounds for tree- like cutting planes proofs. InProceedings 9th Annual IEEE Symposium on Logic in Computer Science (LICS ’94), pages 220–228, 1994.doi:10.1109/LICS.1994.316069

work page doi:10.1109/lics.1994.316069 1994
[34]

Proof complexity of natural formulas via communication arguments

Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. InProceedings of the 36th Computational Complexity Conference (CCC ’21), pages 3:1–3:34, 2021.doi:10.4230/LIPIcs.CCC.2021.3

work page doi:10.4230/lipics.ccc.2021.3 2021
[35]

Resolution over linear equations modulo two.Annals of Pure and Applied Logic, 171(1):102722, 2020

Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two.Annals of Pure and Applied Logic, 171(1):102722, 2020. Preliminary version inMFCS ’14.doi: 10.1016/J.APAL.2019.102722

work page doi:10.1016/j.apal.2019.102722 2020
[36]

Clique problem, cutting plane proofs and communication complexity.Informa- tion Processing Letters, 112(20):772–777, 2012.doi:10.1016/j.ipl.2012.07.003

Stasys Jukna. Clique problem, cutting plane proofs and communication complexity.Informa- tion Processing Letters, 112(20):772–777, 2012.doi:10.1016/j.ipl.2012.07.003

work page doi:10.1016/j.ipl.2012.07.003 2012
[37]

Karp.Reducibility among Combinatorial Problems, pages 85–103

Richard M. Karp.Reducibility among Combinatorial Problems, pages 85–103. Springer US, 1972.doi:10.1007/978-1-4684-2001-2_9. 30

work page doi:10.1007/978-1-4684-2001-2_9 1972
[38]

Cambridge University Press, 2019.doi:10.1017/9781108242066

Jan Kraj´ ıˇ cek.Proof Complexity, volume 170 ofEncyclopedia of Mathematics and Its Applica- tions. Cambridge University Press, 2019.doi:10.1017/9781108242066

work page doi:10.1017/9781108242066 2019
[39]

Cambridge University Press, 1997.doi:10.1016/S0065-2458(08)60342-3

Eyal Kushilevitz and Noam Nisan.Communication Complexity. Cambridge University Press, 1997.doi:10.1016/S0065-2458(08)60342-3

work page doi:10.1016/s0065-2458(08)60342-3 1997
[40]

SIAM Journal on Optimization 11(3), 796–817 (2001) https://doi.org/10.1137/S1052623400366802

Jean B. Lasserre. Global optimization with polynomials and the problem of moments.SIAM Journal on Optimization, 11(3):796–817, 2001.doi:10.1137/s1052623400366802

work page doi:10.1137/s1052623400366802 2001
[41]

Cliques enumeration and tree-like resolution proofs.Information Processing Letters, 135:62–67, 2018.doi:10.1016/J.IPL.2018.03.001

Massimo Lauria. Cliques enumeration and tree-like resolution proofs.Information Processing Letters, 135:62–67, 2018.doi:10.1016/J.IPL.2018.03.001

work page doi:10.1016/j.ipl.2018.03.001 2018
[42]

The complexity of proving that a graph is Ramsey.Combinatorica, 37(2):253–268, 2017

Massimo Lauria, Pavel Pudl´ ak, Vojtˇ ech R¨ odl, and Neil Thapen. The complexity of proving that a graph is Ramsey.Combinatorica, 37(2):253–268, 2017. Preliminary version inICALP ’13. doi:10.1007/S00493-015-3193-9

work page doi:10.1007/s00493-015-3193-9 2017
[43]

Cambridge University Press, 2017

Michael Mitzenmacher and Eli Upfal.Probability and computing: Randomization and prob- abilistic techniques in algorithms and data analysis. Cambridge University Press, 2017. doi:10.1017/CBO9780511813603

work page doi:10.1017/cbo9780511813603 2017
[44]

Large clique is hard on average for resolution

Shuo Pang. Large clique is hard on average for resolution. InInternational Computer Science Symposium in Russia (CSR ’21), pages 361–380, 2021.doi:10.1007/978-3-030-79416-3_22

work page doi:10.1007/978-3-030-79416-3_22 2021
[45]

An improved cutting plane method for convex optimization, convex-concave games, and its applications , booktitle =

Anup Rao and Amir Yehudayoff.Communication Complexity and Applications. Cambridge University Press, 2020.doi:10.1145/3357713.3384286

work page doi:10.1145/3357713.3384286 2020
[46]

Razborov

Alexander A. Razborov. Lower bounds on the monotone complexity of some boolean functions. Doklady Akademii Nauk SSSR, 1985.doi:10.1007/bf01157687

work page doi:10.1007/bf01157687 1985
[47]

Searching for falsified clause in random (logn)-CNFs is hard for randomized communication

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan. Searching for falsified clause in random (logn)-CNFs is hard for randomized communication. InProceedings of the 29th International Conference on Randomization and Computation (RANDOM ’25), pages 64:1–64:17, 2025.doi:10.4230/LIPIcs.APPROX/RANDOM.2025.64

work page doi:10.4230/lipics.approx/random.2025.64 2025
[48]

On the constant-depth complexity ofk-clique

Benjamin Rossman. On the constant-depth complexity ofk-clique. InProceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC ’08), pages 721–730, 2008. doi:10.1145/1374376.1374480

work page doi:10.1145/1374376.1374480 2008
[49]

The monotone complexity ofk-clique on random graphs.SIAM Journal on Computing, 43(1):256–279, 2014

Benjamin Rossman. The monotone complexity ofk-clique on random graphs.SIAM Journal on Computing, 43(1):256–279, 2014. Preliminary version inFOCS ’10.doi:10.1137/110839059

work page doi:10.1137/110839059 2014
[50]

Dag-like communication and its applications

Dmitry Sokolov. Dag-like communication and its applications. InProceedings of the 12th In- ternational Computer Science Symposium in Russia (CSR ’17), volume 10304 ofLecture Notes in Computer Science, pages 294–307. Springer, 2017.doi:10.1007/978-3-319-58747-9_26

work page doi:10.1007/978-3-319-58747-9_26 2017
[51]

Random (logn)-CNF are hard for cutting planes (again)

Dmitry Sokolov. Random (logn)-CNF are hard for cutting planes (again). InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), pages 2008–2015, 2024.doi:10.1145/3618260.3649636. 31

work page doi:10.1145/3618260.3649636 2008
[52]

Communication lower bounds for collision problems via density increment arguments

Guangxu Yang and Jiapeng Zhang. Communication lower bounds for collision problems via density increment arguments. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), pages 630–639, 2024.doi:10.1145/3618260.3649607

work page doi:10.1145/3618260.3649607 2024
[53]

Andrew C. Yao. Lower bounds by probabilistic arguments. InProceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS ’83), pages 420–428, 1983.doi: 10.1109/SFCS.1983.30

work page doi:10.1109/sfcs.1983.30 1983
[54]

Theory Comput

David Zuckerman. Linear degree extractors and the inapproximability of max clique and chro- matic number.Theory of Computing, 3(6):103–128, 2007.doi:10.4086/TOC.2007.V003A006. 32

work page doi:10.4086/toc.2007.v003a006 2007