[Proof Complexity] Seminar Mon Nov 22 at 14:00 with Mika Göös: Resolution, Sherali-Adams, and TFNP

[Jakob Nordström]

Dear all,

On Monday November 22 at 14:00 we will have the pleasure of listening to a seminar by Mika Göös at EPFL titled "Resolution, Sherali-Adams, and TFNP". Please see the bottom of this message for the abstract.

We will meet 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 for people who would like to hear the talk but cannot attend.

More information about upcoming video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ or https://calendar.google.com/calendar/u/0?cid=OTgzYmk1dTZwY21wbDVmbGxtOGtwZGg2djBAZ3JvdXAuY2FsZW5kYXIuZ29vZ2xlLmNvbQ . In particular, tomorrow Monday November 8 at 14:00 (standard CET, not daylight saving time) Sajin Koroth at Simon Fraser University is giving a seminar "Lifting with inner-product and other low discrepancy gadgets", on Friday November 12 Nutan Limaye at the IT University of Copenhagen will be speaking about "Superpolynomial lower bounds against low-depth algebraic circuits", and on Wednesday November 17 Elina Rönnberg at Linköping University will be giving a talk "Decomposition approaches for a large-scale scheduling problem". If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

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 an 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.)

Best regards,
Jakob Nordström

**********

Monday Nov 22 at 14:00
Resolution, Sherali-Adams, and TFNP
(Mika Göös, EPFL)

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: There are n-variate CNF contradictions F that can be refuted by constant-width Resolution, but any n^o(1)-degree SA refutation of F requires coefficients of magnitude exp(n^Omega(1)). As an application, we show that relative to an oracle, the search problem class PLS is incomparable to PPADS. In particular, we show that the decision tree analogue of PPADS is captured by SA with small coefficients.

Joint work with Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao.


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