[Proof Complexity] MIAO seminar Thu May 16 at 14:30 CEST with Noah Fleming: PPP is not Turing-closed in the black-box setting

[Jakob Nordström]

Dear all,

On Thursday May 16 at 14:30 CEST (note the time!) we will have the opportunity to enjoy a seminar with Noah Fleming from Memorial University, who will give a talk titled "PPP is not Turing-closed in the black-box setting". 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 seminar room N116A at Universitetsparken 1. 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, 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, and that listeners who got particularly interested will then get have the chance to really get into the technical details during the second half. (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 https://jakobnordstrom.se/miao-seminars/. 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

**********

Thursday May 16 at 14:30 CEST in seminar room N116A, Universitetsparken 1, University of Copenhagen, and on Zoom
PPP is not Turing-closed in the black-box setting
(Noah Fleming, Memorial University)

The TFNP class PPP contains total search problems which are reducible to finding a collision in an exponential-size instance of the pigeonhole principle. PPP is one of the "original five" subclasses of TFNP, and has been extensively studied due to the strong connections between its defining problem — the pigeonhole principle — and problems in cryptography, extremal combinatorics, proof complexity, and other fields. However, despite its importance, PPP appears to be less robust than other important TFNP subclasses. In particular, Buss and Johnson conjectured that PPP is not closed under Turing reductions, and they called for a black-box separation in order to provide evidence for this conjecture, and this conjecture was further highlighted by Daskalakis in his recent IMU Abacus Medal Lecture. This is in contrast to all other major TFNP subclasses, which are known to be closed under Turing reductions.

In this talk we will discuss our recent work, showing that PPP is indeed not Turing-closed in the black-box setting, affirmatively resolving the above conjecture and providing strong evidence that PPP is not Turing-closed. Our proof requires developing new tools for PPP lower bounds, and creates new connections between PPP and the theory of pseudo-expectation operators used for Sherali-Adams and Sum-of-Squares lower bounds in proof complexity.

This talk will be mostly self-contained, assuming only familiarity with NP. Based on joint work with Stefan Grosser, Toniann Pitassi, and Robert Robere.


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