Computer Science/Discrete Mathematics Seminar II

In this talk, we will discuss new algorithms for solving instances of random and semirandom planted constraint satisfaction problems (CSPs). Random CSP are generated by first choosing a solution x and then sampling constraints so that x satisfies every constraint, while semirandom CSPs are hybrid instances that have both worst-case (NP-hard) and average-case (random) structure. Along the way, we will also discuss new algorithms for solving noisy instances of k-sparse linear equations over F_2, or equivalently the sparse Learning Parity with Noise problem in cryptography.

Based on joint work with Arpon Basu, Venkatesan Guruswami, Jun-Ting (Tim) Hsieh, Pravesh K. Kothari, and Andrew D. Lin.