Computer Science/Discrete Mathematics Seminar I | |

Topic: | The deterministic communication complexity of approximate fixed point |

Speaker: | Omri Weinstein |

Affiliation: | New York University |

Date: | Monday, February 22 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2016/0222-Weinstein |

We study the two-party communication complexity of the geometric problem of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions $g \circ f$, where Alice knows $f$ and Bob knows $g$. We prove an essentially tight deterministic communication lower bound on this problem, using a novel adaptation of the Raz-McKenzie simulation theorem into geometric settings, allowing us to "lift" the *query* lower bound of approximate fixed-point ([HPV89]) from the oracle model to the two-party model in a "smooth" fashion. We show that a slightly "smoother" version of our lower bound would imply an essentially tight communication lower bound on the problem of finding an approximate Nash equilibrium, both in 2-player and $n$-player games, assuming each player initially knows only his own payoff matrix. Such result would exhibit an exponential separation between deterministic and non-deterministic communication, in contrast to the exact equilibrium case (Hart and Mansour, STOC 2007). Joint work with Tim Roughgarden.