ECCC-Report TR16-055https://eccc.weizmann.ac.il/report/2016/055Comments and Revisions published for TR16-055en-usTue, 12 Apr 2016 20:46:08 +0300
Paper TR16-055
| On the Communication Complexity of Approximate Fixed Points |
Omri Weinstein,
Tim Roughgarden
https://eccc.weizmann.ac.il/report/2016/055 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)$).
Tue, 12 Apr 2016 20:46:08 +0300https://eccc.weizmann.ac.il/report/2016/055