Seminars & Colloquia Calendar

We present a new methodology for proving distribution testing lowerbounds, establishing a connection between distribution testing and thesimultaneous message passing (SMP) communication model. Extending theframework of Blais, Brody, and Matulef [BBM12], we show a simple way toreduce (private-coin) SMP problems to distribution testing problems.This method allows us to prove several new distribution testing lowerbounds, as well as to provide simple proofs of known lower bounds.

Our main result is concerned with testing identity to a specificdistribution p, given as a parameter. In a recent and influential work,Valiant and Valiant [VV14] showed that the sample complexity of theaforementioned problem is closely related to the 2/3-quasinorm of p. Weobtain alternative bounds on the complexity of this problem in terms ofan arguably more intuitive measure and using simpler proofs. Morespecifically, we prove that the sample complexity is essentiallydetermined by a fundamental operator in the theory of interpolation ofBanach spaces, known as Peetre's K-functional. We show that thisquantity is closely related to the size of the effective support of p(loosely speaking, the number of supported elements that constitute thevast majority of the mass of p). This result, in turn, stems from anunexpected connection to functional analysis and refined concentrationof measure inequalities, which arise naturally in our reduction.

Joint work with Eric Blais (University of Waterloo) and Tom Gur(Weizmann Institute)