Rectangles Are Nonnegative Juntas
Rectangles Are Nonnegative Juntas
复制标题
矩形是非负 Juntas
DOI：
10.1145/2746539.2746596
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
Mika Göös;Shachar Lovett;Raghu Meka;Thomas Watson;David Zuckerman
我们开发了一种新方法，以证明f gn形式的函数的通信下限，其中f是n输入上的任何布尔函数，而g是一个足够的“硬”两派对小工具。 F O GN的通信矩阵可以通过Juntas的非负组合来模拟。 G。绑定和扩展差异作为应用程序，我们从先前工作中解决了几个开放问题：我们表明SBPCC（以腐败为特征）交点是立即的推论回答Kol等人的问题。
We develop a new method to prove communication lower bounds for composed functions of the form f o gn where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f o gn can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o gn in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.
影响因子：
1.4
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas