The Partition Bound for Classical Communication Complexity and Query Complexity
The Partition Bound for Classical Communication Complexity and Query Complexity
复制标题
经典通信复杂性和查询复杂性的分区界限
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
H. Klauck
中科院分区：
文献类型：
--
作者：
Rahul Jain;H. Klauck
我们描述了随机通信复杂性和查询复杂性的新界限，我们称它们为线性程序的最佳值。 γ2/广义差异界限。 。
We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the γ2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than the approximate polynomial degree and adversary bounds.