Statistical Algorithms and Planted Cliques

In this talk, I will present a framework for analyzing a wide range of computational problems over distributions. I will define a class of algorithms called statistical algorithms, which captures most natural methods used in theory and practice. I will discuss how this lens can help us analyze many well-known combinatorial and optimization problems and give lower bounds on the complexity of any statistical algorithm for them. These include a nearly optimal lower bound for detecting planted clique distributions, a problem that arises in many areas. This work begins to explain this problem's hardness and also sheds light on how we can hope to make progress in devising new optimization algorithms. Time permitting, I will also discuss algorithms and potential lower bounds for planted partition problems. Random linear systems and computational learning theory will also make an appearance.

This talk mainly covers work joint with Vitaly Feldman, Elena Grigorescu, Santosh Vempala, and Ying Xiao, and also touches on work with Sam Cole and Shmuel Friedland.