| Title | : | Distribution Testing under Memory Constraints |
| Speaker | : | Sampriti Roy (IITM) |
| Details | : | Thu, 12 Jun, 2025 3:30 PM @ Online |
| Abstract: | : | Distribution testing deals with understanding whether an unknown distribution satisfies a property or far from it by drawing an optimal number of samples from the distribution. We study distribution testing under memory constraints in both standard and conditional access models. We establish sample-space trade-offs for testing identity and monotonicity, and generalize our approach for testing a larger class of decomposable distributions. We further develop constant-memory algorithms for estimating distance to uniformity and distance to a known distribution. We also present space-efficient algorithms for testing properties of distributions with structural restrictions. Additionally, we extend our techniques to the distributed setting, and present communication-efficient algorithms for key distribution testing tasks. |
