期刊
SIAM JOURNAL ON COMPUTING
卷 40, 期 6, 页码 1969-2000出版社
SIAM PUBLICATIONS
DOI: 10.1137/080733644
关键词
pattern matrix method; bounded-error communication complexity; quantum communication complexity; discrepancy; Degree/Discrepancy Theorem; approximate rank; approximate trace norm; linear programming duality; approximation and sign-representation of Boolean functions by real polynomials
资金
- NSF [CCF-0728536]
We develop a novel technique for communication lower bounds, the pattern matrix method. Specifically, fix an arbitrary function f : {0, 1}(n) -> {0, 1}, and let A(f) be the matrix whose columns are each an application of f to some subset of the variables x(1), x(2), ... , x(4n). We prove that A(f) has bounded-error communication complexity Omega(d), where d is the approximate degree of f. This result remains valid in the quantum model, regardless of prior entanglement. In particular, it gives a new and simple proof of Razborov's breakthrough quantum lower bounds for disjointness and other symmetric predicates. We further characterize the discrepancy, approximate rank, and approximate trace norm of A(f) in terms of well-studied analytic properties of f, broadly generalizing several recent results on small-bias communication and agnostic learning. The method of this paper has also enabled important progress in multiparty communication complexity.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据