Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Vitaly Feldman, Elena Grigorescu, Lev Reyzin +2

We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle…