期刊
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING
卷 -, 期 -, 页码 257-266出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2746539.2746596
关键词
Communication complexity; Query complexity
资金
- NSF CAREER award [1350481]
- NSF [CCF-1218723]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1218723] Funding Source: National Science Foundation
We develop a new method to prove communication lower bounds for composed functions of the form f circle g(n) 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 circle g(n) 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 circle g(n) 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 SBP (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MA(cc) not equal 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 2014) for partial matrices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据