[Proof Complexity] MIAO seminar Friday Nov 25 at 14:00 CET with Shuo Pang: SoS degree lower bound for exact clique

[Jakob Nordström]

Dear all,

On Friday November 25 at 14:00 it is a great joy to introduce our new postdoc Shuo Pang, who will tell us about some of his work on the Sums-of-Squares proof system. Shuo's talk is titled "SoS degree lower bound for exact clique" and you find the abstract at the bottom of this message.

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://youtube.com/@MIAOresearch (where, incidentally, a number of seminar videos from earlier this autumn and summer have recently 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/ . In particular, don't miss the seminar with Kilian Risse on Monday November 21! If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Friday Nov 25 at 14:00 CET in Copenhagen and on Zoom
SoS degree lower bound for exact clique
(Shuo Pang, University of Copenhagen)

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.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se