2025/07/14 by Basu, Arpon, Hsieh, Jun-Ting, Lin, Andrew D. +1 · 1 voice
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.10833
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 nO(ℓ) 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 [FPV15], the case of ℓ = O(1), to larger runtimes, and matches the constraint number vs. runtime trade-off established for refuting random CSPs by [RRS17]. Our algorithm is conceptually different from the recent algorithm of [GHKM23], which gave a poly(n)-time algorithm to solve semirandom CSPs with m ≥ O(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.