31 March 2026, Computational Social Choice Seminar, Paul Goldberg

An unambiguous problem is a computational search problem for which any instance has at most one solution. We are interested in particular in problems where this uniqueness of solutions is due to the structure of the problem itself, as opposed to being due to a (hard to verify) promise that any solution is unique. There are not many such problems in the class NP (amongst problems that are not known to be polynomial-time solvable), but there are various interesting ones in the class Σ^P_2. For example, some are based on the idea that we can design competitions for which there is at most one winner. With exponentially-many competitors, we seek a competitor that beats all his opponents: if "beats" is checkable in polynomial time, we have a Σ^P_2 problem having at most one solution. Towards classifying the complexity of these problems, we introduce complexity classes "Polynomial Tournament Winner" and "Polynomial Condorcet Winner".

This is joint work in progress with Matan Gilboa, Elias Koutsoupias, and Noam Nisan. I will try to include reminders of definitions of any complexity classes I refer to, apart from P and NP.