Abstract

We define a new complexity class TFAP to capture TFNP problems that possess abundant solutions for each input. The canonical example of a TFAP problem is WeakPigeon --- finding a collision in a mapping from 2n pigeons to n holes. We build a general framework that separates TFAP with the rest of the TFNP world in the black-box setting. As a corollary, UEOPL is not in PWPP in the black-box setting.

Based on recent works: Total NP Search Problems with Abundant Solutions. To appear in ITCS-24.

Time

2024-01-03  14:00 - 15:00   

Speaker

Jiawei Li, UT Austin

Room

Room 308