Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-055 | 11th April 2016 09:30

On the Communication Complexity of Approximate Fixed Points



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 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 $\epsilon=\Omega(1/\log^2 N)$-approximate
Nash equilibrium in an $N\times N$ bimatrix game (where each player knows only his own payoff matrix) is at least
$N^\gamma$ for some constant $\gamma>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 $\epsilon=\Omega(1)$-Nash
equilibrium in a $k$-player constant-action game is at least $2^{\Omega(k/\log k)}$ (while the nondeterministic
communication complexity is only $O(k)$).

ISSN 1433-8092 | Imprint