Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
Characterizing the computational complexity of statistical inference problems is an outstanding open problem. This is gaining increasing importance given the ubiquity of large scale data analysis and algorithms in application domains as diverse as genomics,…