|Computer Science/Discrete Mathematics Seminar I|
|Topic:||The deterministic communication complexity of approximate fixed point|
|Affiliation:||New York University|
|Date:||Monday, February 22|
|Time/Room:||11:15am - 12:15pm/S-101|
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.