Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

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

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)

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.