[Colloquium] UC Theory Seminar - Mika Göös, Tuesday, October 18, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Mika Göös
The Swiss Federal Institute of Technology in Lausanne, Switzerland


[image001.jpg]

Tuesday, October 18, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107


TITLE:  Separations in Proof Complexity and TFNP

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: 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 total NP search problems. First, we characterise the classes PPADS, PPAD, SOPL by unary-SA, unary-NS, and Reversible Resolution, respectively. Second, we show that, relative to an oracle, PLS not-subset PPP, SOPL not-subset PPA, and EOPL not-subset UEOPL. In particular, together with prior work, this gives a complete picture of the black-box relationships between all classical TFNP classes introduced in the 1990s.

Bio:  I am an assistant professor at EPFL in the Theory Group. Previously, I was a post-doc at Stanford, Princeton IAS, and Harvard.








HOST: Alexander Razborov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221013/c51447a1/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 66875 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221013/c51447a1/attachment-0001.jpg>