COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | Testing Symmetric Properties of Distributions |

Speaker: | Paul Valiant |

Affiliation: | Massachusetts Institute of Technology |

Date: | Monday, March 24 |

Time/Room: | 11:15am - 12:15pm/S-101 |

We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that ``a distribution property in the class is testable if and only if the Canonical Tester tests it''. We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy $<\alpha$ or $>\beta$ on distributions over $[n]$ requires $n^{\alpha/\beta- o(1)}$ samples, and distinguishing whether a pair of distributions has statistical distance $<\alpha$ or $>\beta$ requires $n^{1-o(1)}$ samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance $>\beta$ requires $\Omega(n^{2/3})$ samples.