From: 2021-11-22 14:00 to 16:00
Place: Online - link by registration
Contact: jakob [dot] nordstrom [at] cs [dot] lth [dot] se
Save event to your calendar

Title: Resolution, Sherali-Adams, and TFNP

Speaker: Mika Göös, EPFL

Host: Jacob Nordström, Department of Computer Science, Lund University Joint with

Where: Online

Abstract

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.

The MIAO video seminars are arranged by the  Mathematical Insights into Algorithms for Optimization (MIAO) research group at the University of Copenhagen and Lund University. Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break an optional 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. For listeners who are particularly interested, there is then an opportunity to return for a second part where we get into more technical details.