A Direct Product Theorem for Discrepancy
A Direct Product Theorem for Discrepancy
复制标题
DOI：
10.1109/ccc.2008.25
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Troy Lee;A. Shraibman;R. Spalek
中科院分区：
文献类型：
--
作者：
Troy Lee;A. Shraibman;R. Spalek
差异是通信复杂性的一个通用界，它可以用来显示随机的、量子的、甚至弱无界的通信错误模型的下界。我们证明了一个关于偏差的最优乘积定理，即对于任意两个布尔函数f，g，Disk(F)=Thetas(Disk(F)Disk(G))。作为结果，我们得到了分布复杂性的一个强直积定理和最坏情况复杂性的直和定理，得到了差异法所示的界。我们的结果解决了Shaltiel(2003)的一个公开问题，他证明了关于均匀分布的偏差的一个较弱的乘积定理，disuot(Fodotk)=O(disu(F))k/3。我们结果的主要工具是半定规划，特别是Linial和Shraibman(2006)最近关于半定规划量的偏差的刻画。
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in randomized, quantum, and even weakly-unbounded error models of communication. We show an optimal product theorem for discrepancy, namely that for any two Boolean functions f, g, disc(f odot g)=thetas(disc(f) disc(g)). As a consequence we obtain a strong direct product theorem for distributional complexity, and direct sum theorems for worst-case complexity, for bounds shown by the discrepancy method. Our results resolve an open problem of Shaltiel (2003) who showed a weaker product theorem for discrepancy with respect to the uniform distribution, discUodot(fodotk)=O(discU(f))k/3. The main tool for our results is semidefinite programming, in particular a recent characterization of discrepancy in terms of a semidefinite programming quantity by Linial and Shraibman (2006).