Communication Complexity of Statistical Distance
Communication Complexity of Statistical Distance
复制标题
统计距离的通信复杂度
DOI：
10.1145/3170708
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Watson, Thomas
中科院分区：
文献类型：
--
作者：
Watson, Thomas
我们证明了以下问题的随机通信复杂度的上界和下界几乎匹配：Alice和Bob都被赋予了一个关于n个元素的概率分布，并且他们希望在±ε内估计他们的分布之间的统计（总变差）距离。对于某些范围的参数，有一个lognfactor之间的差距上限和下限，我们确定了一个障碍，使用信息复杂性技术，以提高在这种情况下的下限。我们还证明了沿着发现的一个副结果：由n位大于组成的n位多数的随机通信复杂度为Θ（nlogn）。
We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution overnelements, and they wish to estimate within ±ε the statistical (total variation) distance between their distributions. For some range of parameters, there is up to a lognfactor gap between the upper and lower bounds, and we identify a barrier to using information complexity techniques to improve the lower bound in this case. We also prove a side result that we discovered along the way: the randomized communication complexity ofn-bit Majority composed withn-bit Greater Than is Θ (nlogn).
登录
查看更多内容
矩形是非负 Juntas
DOI：
10.1145/2746539.2746596
发表时间：
2015
期刊：
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Mika Göös;Shachar Lovett;Raghu Meka;Thomas Watson;David Zuckerman
通讯作者：
David Zuckerman
通过零通信协议和应用程序降低信息复杂性
DOI：
10.1109/focs.2012.68
发表时间：
2012
期刊：
2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Iordanis Kerenidis;Sophie Laplante;Virginie Lerays;J. Roland;David Xiao
通讯作者：
David Xiao
估计最小熵的复杂性
影响因子：
1.4
作者：
Thomas Watson
通讯作者：
Thomas Watson
影响因子：
1.1
作者：
M. Braverman;Omri Weinstein
通讯作者：
Omri Weinstein
DOI：
--
发表时间：
2009
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
Rahul Jain;H. Klauck
通讯作者：
H. Klauck