Combinatorics Seminar - Alexandros Hollender

16:15-18:00

Speaker: Alexandros Hollender

Title: Pure-Circuit: Strong Inapproximability for PPAD

Abstract: PPAD is a complexity class that contains search problems that are guaranteed to always have a solution. Due to its close connection with topological tools such as Brouwer's fixed point theorem, it has emerged as the class characterizing the complexity of many fundamental problems in game theory and economics. In this talk, I will introduce the Pure-Circuit problem: a new tool for proving hardness of approximation for problems in the class PPAD. We will see how this new technique can be used to show tight inapproximability results for various Nash equilibrium computation problems.

Based on joint work with Argyrios Deligkas, John Fearnley, and Themistoklis Melissourgos.