MIAO Talk by Shuo Pang

Abstract:

Consider the claim that "the graph G is w-clique-free", where w is a fixed parameter greater than, say, 2 log n. We know by simple counting that the claim is true with high probability over G ∼ G(n,1/2), but how about proving it for the given sample G — is it almost always hard?

A closely related algorithmic problem is called planted clique. 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)?

After a long line of work, it turns out w=sqrt(n) is essentially the optimal value that SoS proofs of a reasonable degree can achieve. I will review the recent strongest version of this result, where SoS could fully employ all the constraints, including the one for the objective value.

About MIAO seminars:

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome on UCPH campus --- the exact location will be communicated later. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A (where, incidentally, a number of seminar videos from earlier this autumn and summer have now finally been published) for people who would like to hear the talk but cannot attend.

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. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn@di.ku.dk.