We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition of two Lipschitz functions g f : [ 0 1 ] n [ 0 1 ] n , where Alice holds f and Bob holds g . We prove an exponential (in n ) lower bound on the deterministic communication complexity of this problem. Our technical approach is to adapt the Raz-McKenzie simulation theorem (FOCS 1999) into geometric settings, thereby "smoothly lifting'' the deterministic \emph{query} lower bound for finding an approximate fixed point (Hirsch, Papadimitriou and Vavasis, Complexity 1989) from the oracle model to the two-party model. Our results also suggest an approach to the well-known open problem of proving strong lower bounds on the communication complexity of computing approximate Nash equilibria. Specifically, we show that a slightly "smoother" version of our fixed-point computation lower bound (by an absolute constant factor) would imply that:

(i) The deterministic two-party communication complexity of finding an = (1 log 2 N ) -approximate Nash equilibrium in an N N bimatrix game (where each player knows only his own payoff matrix) is at least N for some constant 0"> 0 . (In contrast, the \emph{nondeterministic} communication complexity of this problem is only O ( log 6 N ) ).

(ii) The deterministic (Number-In-Hand) multiparty communication complexity of finding an = (1) -Nash equilibrium in a k -player constant-action game is at least 2 ( k log k ) (while the nondeterministic communication complexity is only O ( k ) ).