
Algorithms for Solving Random and Semirandom Planted Constraint Satisfaction Problems
Peter Manohar of the Institute for Advanced Study presents new algorithmic results for random and semirandom planted constraint satisfaction problems. Random CSPs are built by first fixing a solution and then sampling constraints it satisfies, while semirandom CSPs mix worst-case, NP-hard structure with average-case randomness. Manohar walks through algorithms that solve both settings, then connects the techniques to noisy k-sparse linear equations over F_2, equivalent to the sparse Learning Parity with Noise problem used in cryptography. The talk draws on joint work with Arpon Basu, Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, and Andrew D. Lin, delivered as part of the IAS Computer Science/Discrete Mathematics Seminar II. It is a technical research seminar aimed at an audience already versed in constraint satisfaction and complexity theory, covering the problem setup, the algorithmic ideas, and their cryptographic implications in detail.