Peter Dixon, 'Distribution Testing and Complexity', TADS Lunch-n-Learn

Thursday, February 6, 2020 - 12:00pm to 1:00pm
Event Type: 

Presenter: Peter Dixon

Title: Distribution Testing and Complexity

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!