Detection of Planted Solutions for Flat Satisfiability Problems

Quentin Berthet, Jordan Ellenberg
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1303-1312, 2019.

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. We introduce a modification of our model, the light planting of solutions, and show that it is as hard as the problem of learning parity with noise. This hints strongly at the difficulty of detecting planted flat satisfiability for a wide class of tests.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-berthet19b, title = {Detection of Planted Solutions for Flat Satisfiability Problems}, author = {Berthet, Quentin and Ellenberg, Jordan}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1303--1312}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/berthet19b/berthet19b.pdf}, url = {https://proceedings.mlr.press/v89/berthet19b.html}, 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. We introduce a modification of our model, the light planting of solutions, and show that it is as hard as the problem of learning parity with noise. This hints strongly at the difficulty of detecting planted flat satisfiability for a wide class of tests.} }
Endnote
%0 Conference Paper %T Detection of Planted Solutions for Flat Satisfiability Problems %A Quentin Berthet %A Jordan Ellenberg %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-berthet19b %I PMLR %P 1303--1312 %U https://proceedings.mlr.press/v89/berthet19b.html %V 89 %X 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. We introduce a modification of our model, the light planting of solutions, and show that it is as hard as the problem of learning parity with noise. This hints strongly at the difficulty of detecting planted flat satisfiability for a wide class of tests.
APA
Berthet, Q. & Ellenberg, J.. (2019). Detection of Planted Solutions for Flat Satisfiability Problems. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1303-1312 Available from https://proceedings.mlr.press/v89/berthet19b.html.

Related Material