Seminars & Colloquia Calendar
Alice and Bob Show Distribution Testing Lower Bounds (They donâ€™t talk to each other anymore.)
Clement Cannone: Columbia University
Location: CoRE 301
Date & time: Wednesday, 01 February 2017 at 11:00AM - 11:11AM
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)