Detection of Planted Solutions for Flat Satisfiability Problems
This addresses the challenge of identifying hidden solutions in generalized satisfiability problems, which is incremental as it builds on existing detection and hardness frameworks.
The paper tackles the problem of detecting planted solutions in random instances of flat satisfiability problems, showing that a modified model called light planting is as hard as learning parity with noise, which strongly hints at the difficulty of detection for many tests.
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.