17252

Video URL

https://simons.berkeley.edu/talks/tbd-269

Total Function Problems in the Polynomial Hierarchy

(2021). Total Function Problems in the Polynomial Hierarchy. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/tbd-269

Total Function Problems in the Polynomial Hierarchy. The Simons Institute for the Theory of Computing, Feb. 18, 2021, https://simons.berkeley.edu/talks/tbd-269 

          @misc{ scivideos_17252,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-269},
            author = {},
            keywords = {},
            language = {en},
            title = {Total Function Problems in the Polynomial Hierarchy},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {17252 see, \url{https://scivideos.org/index.php/Simons-Institute/17252}}
          }
Christos Papadimitriou (Columbia University)
Talk number17252
Source RepositorySimons Institute
Subject

Abstract

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.