Modern Challenges in Distribution Testing

Abstract: Given samples from an unknown distribution p, does it satisfy some hypothesis? This question has received enormous attention in statistics, information theory, and theoretical computer science. Classically, hypothesis testing has been studied in the asymptotic setting. However, a flurry of recent work has focused on non-asymptotic setting, and determining the sample complexity required to achieve non-trivial error rates. In my thesis, I develop methods for hypothesis testing in a number of settings of modern interest, with a focus on sample and computational efficiency. Some settings considered include testing against composite hypotheses, testing with multivariate data, testing on sensitive data, and testing when we have stronger access to the underlying distribution. I will discuss our results as well as interesting directions for future study.