Some Pigeons are More Equal than Others --- On Pigeonhole Principles in TFNP
- Jiawei Li, UT Austin
- Time: 2023-12-22 15:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
In this talk, we will present two recent developments on the complexity of pigeonhole principle within TFNP.
In the first half of the talk, we focus on the complexity of generalized pigeonhole principle, with its application on Ramsey, cryptography, and quantum complexity. The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t+1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a new hierarchy of classes defined by the problems t-PPP. In particular, we prove that RAMSEY is not in t-PPP in the black-box setting for any sub-polynomial t. This refutes a conjecture by Goldberg and Papadimitriou in the black-box setting.
We turn our attention to the weak pigeonhole principle in the second half. 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 two recent works:
"On Pigeonhole Principles and Ramsey in TFNP" with Siddharthat Jain, Robert Robere, and Zhiyang Xun. In submission.
"Total NP Search Problems with Abundant Solutions". To appear in ITCS-24.
Biography
Jiawei Li is a third year CS Ph.D. student at UT Austin, advised by Prof. Scott Aaronson. He is interested in computational complexity, especially on total NP search problems (TFNP). He is also interested in quantum query complexity.