Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

Abstract: We present an efficient algorithm to solve semi-random planted instances of any Boolean constraint satisfaction problem (CSP). The semi-random model is a hybrid between worst-case and average-case input models, where the input is generated by (1) choosing an arbitrary planted assignment x∗, (2) choosing an arbitrary clause structure, and (3) choosing literal negations for each clause from an arbitrary distribution "shifted by x∗" so that x∗ satisfies each constraint. For an n variable semi-random planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but an o(1)-a fraction of constraints, provided that the instance has at least Õ (nk/2) constraints. This matches, up to polylog(n) factors, the clause threshold for algorithms that solve fully random planted CSPs [FPV15] and algorithms that refute random and semi-random CSPs. Our result shows that despite having a worst-case clause structure, the randomness in the literal patterns makes semi-random planted CSPs significantly easier than worst-case, where analogous results require O(n^k) constraints.
Perhaps surprisingly, our algorithm follows a conceptual framework different from the recent resolution of semi-random CSP refutation. This turns out to be inherent and, at a technical level, can be attributed to the need for relative spectral approximation of certain random matrices - reminiscent of the classical spectral sparsification - which ensures that an SDP can certify the uniqueness of the planted assignment. In contrast, in the refutation setting, obtaining a weaker guarantee of absolute upper bounds on the spectral norm of related matrices suffices.
Based on joint work with Venkatesan Guruswami, Jun-Ting Hsieh, and, Peter Manohar

Bio: Pravesh Kothari is an Assistant Professor of Computer Science at Princeton University. Earlier, he was an Assistant Professor at Carnegie Mellon University's CS Department, a Postdoctoral Research Instructor at Princeton CS and the School of Math at the IAS, and obtained his Ph.D. from UT Austin in 2016. Dr. Kothari's research interests span several topics in theoretical computer science such as convex optimization and applications to algorithm design, algorithms and lower bounds for statistical estimation and average-case combinatorial optimization, and spectral methods and connections to random matrix theory, coding theory and extremal combinatorics. His research has been recognized with a Simons Award for graduate students (2014), a Google Research Scholar Award (2022), an IIT Kanpur Young Alumnus Award (2023), an NSF CAREER Award (2021), an Alfred P. Sloan Research Fellowship (2021), and the EATCS Presburger Award (2024).