Search Results

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 generated by (1) choosing an arbitrary planted assignment x^*, and then (2) sampling constraints from a particular "planting distribution" designed so that x^* will satisfy every constraint. Given an n variable instance of a k-ary Boolean CSP with m constraints, our algorithm runs in time n^O(𝓁) for a choice of a parameter 𝓁, and succeeds in outputting a satisfying assignment if m ⩾ O(n)⋅(n/𝓁)^{k/2 - 1} log n. This generalizes the poly(n)-time algorithm of [Vitaly Feldman et al., 2015], the case of 𝓁 = O(1), to larger runtimes, and matches the constraint number vs. runtime trade-off established for refuting random CSPs by [Prasad Raghavendra et al., 2017]. Our algorithm is conceptually different from the recent algorithm of [Venkatesan Guruswami et al., 2023], which gave a poly(n)-time algorithm to solve semirandom CSPs with m ⩾ Õ(n^{k/2}) constraints by exploiting conditions that allow a basic SDP to recover the planted assignment x^* exactly. Instead, we forego certificates of uniqueness and recover x^* in two steps: we first use a degree-O(𝓁) Sum-of-Squares SDP to find some x̂ that is o(1)-close to x^*, and then we use a second rounding procedure to recover x^* from x̂.