Quentin Berthet

Monday, December 1, 2014 - 4:15pm to 5:30pm
California Institute of Technology
Optimal Testing for Planted Satisfiability Problems
We consider the problem of detecting planted solutions in a random satisfiability formula. Adopting the formalism of hypothesis testing in statistical analysis, we describe the minimax optimal rates of detection. Our analysis relies on the study of the number of satisfying assignments, for which we prove new results. We also address algorithmic issues by describing the performance of a new computationally efficient test. This result is compared to a related hypothesis of Feige on the hardness of detecting satisfiability of random formulas, in order to investigate the interplay between computational and statistical efficiency.