Published 2015
| Published + Submitted
Journal Article
Open
Optimal testing for planted satisfiability problems
- Creators
- Berthet, Quentin
Abstract
We study 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, and give a computationally efficient test with optimal statistical performance. This result is compared to an average-case hypothesis on the hardness of refuting satisfiability of random formulas.
Additional Information
© 2015 Institute of Mathematical Statistics. Received May 2014. The author thanks Philippe Rigollet, Emmanuel Abbé, Dan Vilenchick and Amin Coja-Oghlan for very helpful discussions. Partially supported by NSF grant CAREER-DMS-1053987 when the author was at Princeton University, and by AFOSR grant FA9550-14-1-0098.Attached Files
Published - euclid.ejs.1425398209.pdf
Submitted - 1401.2205v3.pdf
Files
euclid.ejs.1425398209.pdf
Files
(444.0 kB)
Name | Size | Download all |
---|---|---|
md5:0fd80c65326d9238790372056392aa17
|
226.0 kB | Preview Download |
md5:02df1392aa2d24ac2078251918dbe389
|
218.0 kB | Preview Download |
Additional details
- Eprint ID
- 63486
- Resolver ID
- CaltechAUTHORS:20160108-092658146
- DMS-1053987
- NSF
- FA9550-14-1-0098
- Air Force Office of Scientific Research (AFOSR)
- Created
-
2016-01-08Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field