Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RAZ-MCKENZIE SIMULATION :
Reports tagged with Raz-McKenzie Simulation :
TR16-055 | 11th April 2016
Tim Roughgarden, Omri Weinstein

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 ... more >>>




ISSN 1433-8092 | Imprint