Theory of Computing Seminar
Detection of Planted Solutions for Flat Satisfiability Problems
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.
Contact: Thomas Vidick email@example.com