skip to main content
Caltech
Fires burning in Greater Los Angeles area have had significant impact on the Caltech's community and surrounding areas. For information and resources for members of the Caltech community, go to https://www.caltech.edu/fire.

Theory of Computing Seminar

Friday, April 17, 2015
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Detection of Planted Solutions for Flat Satisfiability Problems
Quentin Berthet, Caltech,

Abstract:

We study the detection problem of finding planted solutions in random instances of flat satisfiability problems, a generalization of boolean satisfiability formulas. We describe the properties of random instances
of flat satisfiability, as well of the optimal rates of detection of the  associated hypothesis testing problem. We also study the performance of an algorithmically efficient testing procedure. Introducing a modification of our model, the light planting of solutions, allows us to hint strongly at the difficulty of detecting planted flat satisfiability for a wide class of tests, by relating this problem to learning parity with noise. 
For more information, please contact Thomas Vidick by email at vidick@cms.caltech.edu.