Algorithms and Complexity Seminar

Thursday, September 27, 2007, 4-5:15pm in 32-G575.

Lower Bounds for Distribution Testing

Paul Valiant (MIT)

We present two general tools for proving lower bounds on the sample complexity of testing symmetric properties of distributions. As an application we prove tight lower bounds that resolve conjectures about the hardness of (1) testing statistical distance, (2) approximating statistical distance, and (3) approximating the entropy of distributions.

Host: Nick Harvey

(The Algorithms and Complexity Seminar series talks are usually held Thursdays from 4-5:15pm in 32-G575.)