[SOLVED] CS Skip to main content

Skip to main content

We gratefully acknowledge support from
the Simons Foundation and member institutions.
arXiv.org > cs > arXiv:0906.4291
Help | Advanced Search
All fields
Title
Author
Abstract
Comments
Journal reference
ACM classification
MSC classification
Report number
arXiv identifier
DOI
ORCID
arXiv author ID
Help pages
Full text

Search
Computer Science > Computational Complexity
[Submitted on 23 Jun 2009]
The Pattern Matrix Method (Journal Version)
Alexander A. Sherstov
We develop a novel and powerful 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 Razborovs 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 recently enabled important progress in multiparty communication complexity.
Comments:
Revised and expanded version of the STOC08 article. To appear in SIAM J. Comput., 2009
Subjects:
Computational Complexity (cs.CC); Quantum Physics (quant-ph)
Cite as:
arXiv:0906.4291 [cs.CC]

(or arXiv:0906.4291v1 [cs.CC] for this version)
Submission history
From: Alexander A. Sherstov [view email]
[v1] Tue, 23 Jun 2009 15:51:36 UTC (58 KB)
Download:
PDF
Other formats
(license)
Current browse context:
cs.CC
<prev | next>
new | recent | 0906
Change to browse by:
cs
quant-ph
References & Citations
INSPIRE HEP
NASA ADS
Google Scholar
Semantic Scholar

DBLP CS Bibliography
listing | bibtex
Alexander A. Sherstov
Export Bibtex Citation
Bookmark

Bibliographic Tools
Bibliographic and Citation Tools

Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Code
Related Papers
About arXivLabs
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

AboutHelp
contact arXivClick here to contact arXivContactsubscribe to arXiv mailingsClick here to subscribeSubscribe
CopyrightPrivacy Policy
Web Accessibility AssistancearXiv Operational Status Get status notifications via email or slack