1 paper
Susanna F. de Rezende, David Engström, Yassine Ghannane +2
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 len…