Computer Science/Discrete Mathematics Seminar I

We study the two-party communication complexity of the geometric problem of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions $g \circ f$, where Alice knows $f$ and Bob knows $g$. We prove an essentially tight deterministic communication lower bound on this problem, using a novel adaptation of the Raz-McKenzie simulation theorem into geometric settings, allowing us to "lift" the *query* lower bound of approximate fixed-point ([HPV89]) from the oracle model to the two-party model in a "smooth" fashion. We show that a slightly "smoother" version of our lower bound would imply an essentially tight communication lower bound on the problem of finding an approximate Nash equilibrium, both in 2-player and $n$-player games, assuming each player initially knows only his own payoff matrix. Such result would exhibit an exponential separation between deterministic and non-deterministic communication, in contrast to the exact equilibrium case (Hart and Mansour, STOC 2007). Joint work with Tim Roughgarden.