[Proof Complexity] MIAO seminar Mon Jan 15 at 14:00 CET with Kilian Risse: The planted clique conjecture holds for unary Sherali-Adams

[Jakob Nordström]

Dear all,

On Monday January 15 at 14:00 CET we will have the opportunity to enjoy a seminar with Kilian Risse from EPFL, who will give a talk titled "The planted clique conjecture holds for unary Sherali-Adams". 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 to auditorium no. 3 in the HCØ Building at Universitetsparken 5. 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 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, our plans for January are as follows:
- Friday Jan 12 at 14:00: Proving UNSAT in zero knowledge (Ning Luo, Northwestern University)
- Monday Jan 15 at 14:00: The planted clique conjecture holds for unary Sherali-Adams (Kilian Risse, EPFL)
- Friday Jan 19 at 14:00: TV distance estimation is as easy as probabilistic inference (Arnab Bhattacharyya, National University of Singapore)
- Monday Jan 29 at 16:00 (note the time!): Fourier growth of communication protocols for XOR functions (Uma Girish, Princeton University)

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

P.S. Apologies for any multiple copies --- the seminar mailing list is not feeling very well right now.

**********

Monday Jan 15 at 14:00 in Auditorium No. 3, Hans Christian Ørsted Building, Universitetsparken 5, University of Copenhagen, and on Zoom
The planted clique conjecture holds for unary Sherali-Adams
(Kilian Risse, EPFL)

We show that the planted clique conjecture holds for any algorithm captured by the linear programming hierarchy Sherali-Adams, if the hierarchy is restricted to represent numbers in unary instead of the usual binary encoding. In a bit more detail, we show that unary Sherali-Adams requires size n^Omega(k) to rule out the existence of an n^0.1-clique in an Erdős-Rényi random graph whose maximum clique is of size k ≤ 2 log n.

In the first hour of the seminar we survey results of a similar flavor, give a high level proof outline and introduce some useful combinatorial concepts. In the second, more technical, part of the seminar we then show how these concepts interact and, if time permits, try to flesh out some details of the proof of key lemmas.

Based on joint work with Susanna de Rezende and Aaron Potechin that appeared in FOCS 2023.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98 / +45 28 78 38 11
https://jakobnordstrom.se