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

by Eric Blais, Clement Canonne, and Tom Gur

#### Oded's comments

Let me highlight two contributions of this paper,
although the paper's abstract kind of does so.
The first contribution is the introduction of a technique for proving
lower bounds on the sample complexity of distribution testing.
The second is in providing an alternative characterization
of the sample complexity of testing equality of a given distribution
to a fixed distribution, where the characterization is in terms of
a *natural* ``measure'' of the fixed distribution
(i.e., the size of its ``effective'' support).

#### The original 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.

See ECCC TR16-168.

Back to
list of Oded's choices.