Low-degree phase transitions for detecting a planted clique in sublinear time

Music City Center 

As the scale of data grows, natural questions arise concerning tension between computation and statistics, and one of the most striking examples of such a phenomenon is the existence of a statistical-computational gap. The prototypical problem exhibiting such a gap is that of planted clique detection in which we aim to detect the presence of a clique of size k in a random graph on n vertices. In this talk, we revisit the question of planted clique detection and consider finer-grained---namely sublinear---notions of computational complexity. Under this lens, we show that much more intricate statistical-computational behavior emerges and demonstrate sharp tradeoffs between signal strength and computational complexity. Joint work with Jay Mardia and Alex Wein.

Statistical-computational gaps

Incomplete data

Sublinear algorithms