Talks
Spring 2021

Total Function Problems in the Polynomial Hierarchy

Thursday, Feb. 18, 2021 8:30 am9:30 am

Add to Calendar

Speaker: 

Christos Papadimitriou (Columbia University)

Location: 

Zoom

The empty pigeonhole principle asserts that, if there are more pigeonholes than pigeons, one pigeonhole must be empty.  The corresponding class of total function problems contains all of FNP, and its natural problems include applications of the union bound and several well known explicit constructions.  Higher up in the polynomial hierarchy, one finds total function problems related to tournaments and the Sauer-Shelah lemma.