Seminar • Algorithms and Complexity • Towards Practical Distribution Testing

Wednesday, April 3, 2024 12:00 pm - 1:00 pm EDT (GMT -04:00)

Please note: This seminar will take place in DC 3317 and online.

Yash Pote, PhD candidate
School of Computing, National University of Singapore

Inferring information about probability distributions with limited samples is a fundamental challenge in computer science. In this talk, we will focus on the problem of estimating the distance between pairs of distributions. Specifically, given distributions P and Q, and a parameter epsilon, we will estimate the total variation distance TV(P, Q) up to an additive tolerance of epsilon. In high dimensions, i.e., when the domain is {0,1}^n for a large n, black-box distance estimation is intractable; hence, richer “grey-box” models, such as conditional sampling, have emerged as promising alternatives. In this talk, I will present our work in developing grey-box estimators that are fast in theory and practice.