Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
It establishes average-case hardness results for proof and communication complexity, relevant to understanding the limits of efficient refutation systems.
The paper proves exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations for the binary encoding of clique formulas on random dense graphs, and shows that the randomized communication complexity of finding a falsified clause is polynomial.
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.