[Proof Complexity] MIAO seminar Mon Feb 6 at 10:00 (note the time!) with Siddhartha Jain: The bridge between proof complexity and TFNP

[Jakob Nordström]

Dear all,

On Monday February 6 at 10:00 (note the time!) we will have the opportunity to enjoy a seminar by Siddhartha Jain from UT Austin, who will give a talk titled "The bridge between proof complexity and TFNP". 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 room A107 in the Hans Christian Ørsted 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, this coming Tuesday January 31 we will have a talk on "Combinatorial problems in algorithmic cheminformatics" by Jakob Lykke Andersen from the University of Southern Denmark, and on Tuesday February 28 we will have a video seminar with Alexander Nadel from Intel and the Technion on the Intel SAT solver. 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

**********

Monday Feb 6 at 10:00 (note the time!) in room A107, Hans Christian Ørsted Building, Universitetsparken 5, University of Copenhagen, and on Zoom
The bridge between proof complexity and TFNP
(Siddhartha Jain, UT Austin)

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: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT Resolution) cannot be efficiently simulated by Nullstellensatz (NS).

These results have consequences for complexity classes of NP search problems that seem surprising at first blush. In particular, the result about Resolution vs Sherali Adams directly implies that the class PLS is not contained in the class PPADS with respect to an oracle. Together with a couple of more observations, we showed all remaining oracle separations between classical TFNP classes introduced in the 1990s.

This is joint work with Mika Göös, Alexandros Hollender, Gilbert Maystre, William Pires, Robert Robere & Ran Tao.

The objective of this talk is to exhibit the tight connection between these two areas, which was made more explicit by a recent paper of Buss, Fleming & Impagliazzo. We will also see how we can use tools from query complexity to answer questions in proof complexity and potentially vice versa. We will also list some open problems in both languages: Proof complexity and TFNP.


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