MIAO Talk by Shuo Pang
Summary
It asks to devise an efficient algorithm whose acceptance rates differ significantly with respect to samples from G(n,1/2) and from G(n,1/2,w), where the latter distribution draws a graph from G(n,1/2) and then independently "plants" a random w-clique. The current state-of-the-art polynomial-time algorithm only succeeds when w is as large as Ω(sqrt(n)), and its correctness relies on degree 2 Sum-of-Squares proofs (SoS). This connection, among others, motivated the study of a cleanly formulated proof-theoretic question: Can higher degree SoS do better on average, i.e., prove "G is w-clique-free" for significantly smaller w and most G from G(n,1/2)? Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details.