Pattern Matrix Method
Pattern Matrix Method
复制标题
模式矩阵法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Nitin Saurabh
中科院分区：
文献类型：
--
作者：
P. Harsha;Nitin Saurabh
这是差异上的逆指数上限，在随机通信成本上具有多项式上限，这种方法的优势之一是，即使是具有非常接近1/2的协议的界限恰好是它无法为功能提供良好界限的原因之一，例如disj，其恒定的位协议最多可以达到1/2 - 1/poly（n）的误差。 DISJ至少为1/poly（n），差异方法不会比随机通信成本上的对数下限更好。普遍的差异方法将有助于解决某些功能的差异方法的这种弱点。复杂性是有意义的。
Thus, an inverse exponential upper bound on the discrepancy gives polynomial upper bounds on the randomized communication cost. In fact, one of the strengths of this approach is that it gives bounds even for protocols with error very close to 1/2. But this also happens to be one of the reasons it fails to give good bounds for functions, such as DISJ, which have constant bit protocols that achieve error at most 1/2 − 1/poly(n). Thus, the discrepancy of DISJ is at least 1/poly(n) and the discrepany method will not give any better than logarithmic lower bound on the randomized communication cost. We will now discuss an extension of the discrepancy method, originally due to Razborov and formalized by Klauck, called the generalized discrepancy method, which will help get around this weakness of the discrepancy approach for certain functions. Let f : X × Y → {1,−1} be a function whose communication complexity is of interest. Suppose there exist h : X × Y → {1,−1} and a distribution μ on X × Y such that the following holds.