We study the two-party communication complexity of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions g*f, where Alice knows f and Bob knows g. We prove an essentially tight deterministic communication lower bound on this problem, using a "geometric" adaptation of the Raz-McKenzie simulation theorem, allowing us to "smoothly lift" the *query* lower bound for approximate fixed-point ([HPV'89]) from the oracle model to the two-party model.

We show that a slightly "smoother" version of our lower bound would imply an N^{Omega(1)} deterministic lower bound on the well known open problem of finding an *approximate* Nash equilibrium in an N*N 2-player game, where each player initially knows only his own payoff matrix. In contrast, the *non-deterministic* communication complexity of this problem is only polylog(N). Such improvement  would also imply an exp(k) communication lower bound for finding an Omega(1)-Nash equilibrium in k-player games.

Joint work with Tim Roughgarden.

Host: Kasper Green Larsen.