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

The authors investigate how hard it is on average to prove that a random dense graph does not contain a large clique, focusing on certain mathematical proof methods and communication tasks. They prove that some common proof techniques require exponentially long explanations to show no large clique exists in these graphs. However, they also find that if two parties try to find an error in these proofs using randomized communication, it can be done with only polynomial effort. This work gives insights into the complexity of reasoning about cliques in random graphs.