CS Peer Talk | Some Pigeons are More Equal than Others

第三十五期

报告人：李佳蔚，UT Austin

时间：12月22日（星期五）3:00pm

地点：静园五院204

报告信息

Title

Some Pigeons are More Equal than Others — On Pigeonhole Principles in TFNP

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 Siddhartha 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.

about CS Peer Talk

作为活动的发起人，我们来自北京大学图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：

• 教程系列：学生讲者为主，介绍自己的研究领域

• 研究系列：学生讲者为主，介绍自己的研究成果

• 客座系列：邀请老师做主题报告

除非报告人特别要求，报告默认是非公开的，希望营造一个自由放松但又互相激励的交流氛围。

主讲嘉宾招募

如果你愿意和大家分享你的学术成果、经历经验，总结回顾、触发新思，欢迎报名自荐。

主讲人报名：发邮件至 cs_research_tc@163.com，写明想讲的题目、内容及时间。

北京大学图灵班科研活动委员会

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。