| Title | : | Optimizing memory and communication for testing and estimating properties of distributions |
| Speaker | : | Sampriti Roy (IITM) |
| Details | : | Thu, 27 Jun, 2024 3:00 PM @ SSB 233 |
| Abstract: | : | Distribution testing is a sub-field of property testing that studies algorithms for testing properties of probability distributions. In this framework, the input is a probability distribution accessible via independently drawn samples from an oracle and the task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure. We study the tolerant testing problem, which involves determining whether an unknown distribution is $epsilon_1$-close to a property or $epsilon_2$-far from it. We also investigate the related problem of estimating distance of an unknown distribution to a given property. We focus on finding a smooth trade-off between sample complexity and space complexity for tolerant testing problems. In particular, we propose a sample-space trade-off for testing tolerant closeness between two unknown distributions. We further explore the distance estimation problems, a challenging aspect of tolerant testing, and develop an algorithm for estimating distance to uniformity using constant memory words. This approach extends to estimating the distance to a known distribution, and also estimating the distance between two unknown distributions. In both the scenarios, our algorithms require only a constant amount of space. Additionally, we expand upon the idea aiming to develop communication efficient algorithms for distance estimation problems. |
