Siu On Chan (Chinese University of Hong Kong)- Sum-of-Squares Refutation of Random k-CSPs
Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares algorithm? A sufficient condition, introduced by Kothari, Mori, O’Donnell, and Wit-mer (STOC 2017), is that every constraint has a t-wise uniform distribution of satisfying assignments. This condition is also necessary for random CSPs given by a predicate and uniformly random literals, due to the SoS refutation of Allen, O’Donnell, and Witmer (FOCS 2015).
An open question is to find a more general sufficient condition, as well as refutation for random CSP not involving literals. We show that for a general random k-CSP, the necessary and sufficient condition is not t-wise uniformity, but t-wise independence. Joint work with Tommaso d’Orsi.
Speakers
Siu Ơn Chan
Siu On Chan works on complexity of constraint satisfaction problems. He got a PhD at UC Berkeley under Luca Trevisan and Elchanan Mossel. He was a postdoc at Microsoft Research New England and an assistant professor at Chinese University of Hong Kong. He won a best paper and best student paper award at STOC 2013.
