WNCG Seminar Series

Friday, April 24, 2015
UTA 7.532

Join CalTech's Dr. Quentin Berthet in this one-hour seminar. 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.


Postdoctoral Fellow
California Institute of Technology

Quentin Berthet is a Postdoctoral Fellow at the Center for the Mathematics of Information and the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is currently hosted by Venkat Chandrasekaran. Dr. Berthet completed his Ph.D. at Princeton University, under the supervision of Philippe Rigollet. His research interests include theoretical statistics, computer science, and the relationships between computational and statistical efficiency.

In 2015, Dr. Berthet will join the Statslab faculty in the Department of Pure Mathematics and Mathematical Stastics at the University of Cambridge, UK.