A tight bound for the clique query problem in two rounds

Uriel Feige, Tom Ferster

We consider a problem introduced by Feige, Gamarnik, Neeman, Rácz and Tetali [2020], that of finding a large clique in a random graph $G\sim G(n,\frac{1}{2})$, where the graph $G$…