The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.
We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>
We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition
of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an
exponential (in $n$) lower bound on the deterministic ...
more >>>