Solving Random Planted CSPs below the $n^{k/2}$ Threshold

Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin +1

We present a family of algorithms to solve random planted instances of any $k$-ary Boolean constraint satisfaction problem (CSP). A randomly planted instance of a Boolean CSP is ge…