2026-09-21T06:25:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26412 2026-09-05T19:42:45Z ddc:004 open_access

Solving Random Planted CSPs Below the n^{k/2} Threshold Basu, Arpon Hsieh, Jun-Ting Lin, Andrew D. Manohar, Peter Random CSPs Sparse Learning Parity with Noise 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̂. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arpon Basu and Jun-Ting Hsieh and Andrew D. Lin and Peter Manohar 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.23 urn:nbn:de:0030-drops-264127 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.23 eng https://creativecommons.org/licenses/by/4.0/legalcode