Abstract: We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom 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 semirandom planted instance of a k-arity CSP, our algorithm runs in polynomial time and outputs an assignment that satisfies all but a o(1)-fraction of constraints, provided that the instance has at least n^{k/2} poly(log n) constraints. This matches, up to polylog(n) factors, the clause threshold for algorithms that solve fully random planted CSPs, as well as recent algorithms that refute random and semirandom CSPs. Our result shows that despite having worst-case clause structure, the randomness in the literal patterns makes semirandom planted CSPs significantly easier than worst-case, where analogous results require almost n^k constraints.

The core of our approach is an algorithm for semirandom noisy 2-XOR based on expander decomposition of the constraint graph and certificates of uniqueness of the SDP solution that allows efficient identification of all corrupted equations inside each piece. The uniqueness certificate relies on spectral sparsification guarantees for a form of correlated subsampling of the constraint graph edges.

Based on joint work with Jun-Ting Hsieh, Pravesh Kothari and Peter Manohar.

Bio: Venkatesan Guruswami is a Professor of Computer Science and Mathematics at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor’s degree from the Indian Institute of Technology, Madras, and his Ph.D. from MIT.

Venkat’s research interests include error-correcting codes, constraint satisfaction, approximate optimization, and computational complexity. He is the Editor-in-Chief of JACM, and was previously president of the Computational Complexity Foundation. Venkat is a recipient of the Presburger Award, a Simons Investigator award, Guggenheim, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and a distinguished alumnus award from IIT Madras. He is a fellow of the ACM, IEEE, and AMS.