多方通信复杂度中,手中数字最小下界简化
该研究使用信息复杂度工具及时间复杂度分析,证明在传递消息模型中,Sey Disjointness 问题及任务分配问题在最坏情况下的时间复杂度下界为 n*k。
May, 2013
本文探讨了在 map-reduce 计算中并行性和通信成本之间的权衡问题,并引入了单轮 map-reduce 计算问题的模型,以发现以分配给一个缩小器的最大输入数为函数的通信成本下界。作者对三个问题进行了分析:找到两个距离为 $d$ 的字符串、在较大的图形中查找三角形和其他模式以及矩阵乘法。
Jun, 2012
本文通过引入高斯空间相关性的几何性质以及概率投影的方法证明了久负盛名的 Gap-Hamming-Distance 问题的随机通信复杂度的最优下界,并由此得出了在数据流模型中多遍通信所需的空间的最优下界。
Sep, 2010
研究如何在分布式网络中学习高维、非参数和结构化(如高斯)分布,并考虑不同通信模型(包括独立、顺序和黑板模型)的交互限制对于最小化风险和 Fisher 信息的影响。
Feb, 2019
在分布式网络中进行参数估计,考虑每个传感器从基础分布中观察独立样本并具有 $k$ 位通信其样本到集中式处理器,该处理器计算所需参数的估计值。我们为一类广泛的损失和分布模型开发极小化风险的下界,并表明在温和的正则条件下,当 $k$ 较小时,通信约束将使有效样本量减少 $d$ 倍,其中 $d$ 是被估计参数的维数。此惩罚随着 $k$ 的增加而以最多指数级别降低,这对某些模型如高维分布估计成立。对于其他模型,我们表明样本量的减少是与 $k$ 线性递减的,例如,当一些次高斯结构可用时。我们将结果应用于具有乘积 Bernoulli 模型、多项式模型、高斯位置模型和逻辑回归的分布式设置中,从而恢复或加强现有结果。
Feb, 2018
针对二人 NxN 游戏的 epsilon-Nash 均衡和 n 人二元动作游戏的 epsilon 弱近似 Nash 均衡,我们证明了通信复杂度的下限是多项式 N 和指数级 n。
Aug, 2016
研究了一个关于 “simulate-and-infer” 的通信受限问题,在只要求每个参与者发送少于 log k 比特给中央仲裁者的情况下,寻找利用最少的参与者,对未知概率分布进行推断的最优策略,表明了 simulate-and-infer 策略是最优采样复杂度的,并提出了一个有效的公共硬币通信协议,可以突破身份测试的通信复杂度下界。
Apr, 2018
本文研究了高维分布统计估计问题的统计误差和通信成本之间的权衡,并提供了分布式稀疏高斯均值估计问题的紧密的权衡分析结果,这直接导致了分布式稀疏线性回归问题的下界,并给出了在稠密情况下均值估计的第一个最优同时协议。
Jun, 2015
本研究证明,匹配问题和点覆盖问题在同时通信模型中的不可承受性根源于基础图形跨机器的对抗性分区,进而展示这两个问题存在随机组分的可组合核的对数 O (n)。
May, 2017