Abstract: Distribution testing is a well studied problem with many applications. The goal is to discover properties of an unknown distribution by taking random samples from it. Normally, distribution testing focuses on the sample complexity of the problem -- that is, how many samples do you need to take relative to the size of the support of the distribution? However, distribution testing problems can also be analyzed by their computational complexity---which complexity classes various distribution testing problems lie? This talk will cover few distribution testing problems and their computational complexities.
Bio: Peter is a graduate student at ISU. He works on algorithms and complexity theory. Sometimes he proves things.
After the presentation, there will be a short time for discussion and questions afterwards. Please feel free to bring your lunch!