The Library
Distribution testing lower bounds via reductions from communication complexity
Tools
Blais, Eric, Canonne, Clément L. and Gur, Tom (2019) Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11 (2). pp. 1-37. 6. doi:10.1145/3305270 ISSN 1942-3454.
|
PDF
WRAP-distribution-testing-lower-bounds-via-reductions-communication-complexity-Gur-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1359Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/3305270
Abstract
We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds.
Our main result is concerned with testing identity to a specific distribution, p, given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the ℓ2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre’s K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Computer science -- Mathematics, Computer algorithms, Computer Communication Networks | ||||||
Journal or Publication Title: | ACM Transactions on Computation Theory | ||||||
Publisher: | ACM | ||||||
ISSN: | 1942-3454 | ||||||
Official Date: | April 2019 | ||||||
Dates: |
|
||||||
Volume: | 11 | ||||||
Number: | 2 | ||||||
Page Range: | pp. 1-37 | ||||||
Article Number: | 6 | ||||||
DOI: | 10.1145/3305270 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Re-use Statement: | © ACM 2019. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computation Theory, 11 (2). pp. 1-37. 6. http://dx.doi.org/10.1145/3305270 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 1 August 2019 | ||||||
Date of first compliant Open Access: | 5 August 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year