Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-168 | 28th July 2017 20:28

#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revision #1
Authors: Eric Blais, Clement Canonne, Tom Gur
Accepted on: 28th July 2017 20:28
Downloads: 375
Keywords:

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 [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove several 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 [VV14] showed that the sample complexity of the aforementioned problem is closely related to the $\ell_{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.

Changes to previous version:

Fixed minor typos, updated references.

### Paper:

TR16-168 | 2nd November 2016 18:31

#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

TR16-168
Authors: Eric Blais, Clement Canonne, Tom Gur
Publication: 2nd November 2016 19:19
Downloads: 1058
Keywords:

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 [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove several 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 [VV14] showed that the sample complexity of the aforementioned problem is closely related to the $\ell_{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.

ISSN 1433-8092 | Imprint