• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on economics and computation >On Communication Complexity of Fixed Point Computation
【24h】

On Communication Complexity of Fixed Point Computation

机译：在通信定点的复杂性计算

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from [0, 1]~n to [0, 1]~n, and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of 2~(Ω(n)) for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. ? Each player is given a function from [0, 1]~n to [0, 1]~(n/2), and their goal is to find an approximate fixed point of the concatenation of the functions. ? Each player is given a function from [0, 1]~n to [0, 1]~n, and their goal is to find an approximate fixed point of the mean of the functions. We show a randomized communication complexity lower bound of 2~(Ω(n)) for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulationT of the d-simplex is publicly known and one player is given a set SA ? T and a coloring function from S_A to {0, . . . ,d/2}, and the other player is given a set S_B ? T and a coloring function from S_B to {d/2+1, . . . ,d}, such that S_A∪˙ S_B = T , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of |T |~(Ω(1)) for the aforementioned problem aswell (whend is large).On the positive side,we showthat if d ≤ 4 then there is a deterministic protocol for the Sperner problem withO((log |T |)~2) bits of communication.
机译：这的不动点定理,任何状态连续函数在一个紧凑的凸空间对自己有一个固定的点。2016年温斯坦(foc)发起的研究在两人定点计算通信模型,每个玩家函数[0,1]~ n [0, 1] ~ n,和他们的目标是找到一个近似不动点的两个函数的组合。一个悬而未决的问题的下界2 ~(Ω(n))(随机)通信这一问题的复杂性,在的范围总搜索参数,使它成为一个问题。我们肯定地回答这个问题。此外,我们引入了两个自然固定两人点问题的沟通模型。1] ~ n [0, 1] ~ (n / 2),和他们的目标是寻找一个近似不动点的连接的功能。函数[0,1]~ n [0, 1] ~ n,和他们的目标是找到一个近似不动点的的均值函数。通信复杂性下界2 ~(Ω(n))对于这些问题(对于一些常数近似因子)。找到一个全色单工的学习Sperner-coloring三角(保证两人由Sperner引理)通信模型:triangulationT的d-simplex都是公开的,一个球员给定一组撒?S_A{0,。给定一组S_B吗?S_B {d / 2 + 1,。,他们的目标是找到一个全色单纯形。复杂度的下界| T | ~(Ω(1))的提到的问题也比(whend很大)。积极的一面,如果d≤4还有我们呢是一个确定性的协议Sperner吗问题无((日志T | |) ~ 2)的沟通。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号