Statistical Algorithms for Planted Satisfiability Problems

I will discuss a general framework originating in learning theory for proving average-case algorithmic lower bounds for the class of “statistical algorithms”. I will then apply this framework to planted random satisfiability problems, for which we can identify a tractability threshold for statistical algorithms. Based on joint work with Vitaly Feldman and Santosh Vempala.