We study the following distribution clustering problem: given a hidden partition of distributions into two groups such that the distributions within each group are identical, and the two distributions corresponding to the two clusters are far apart, the goal is to recover the partition. We establish upper and lower bounds on the sample complexity for two fundamental cases: (1) when one of the cluster distributions is known, and (2) when both distributions are unknown.  Our upper and lower bounds characterize the sample complexity’s dependence on the domain size n, number of distributions k, size of one of the cluster r and distance ε.  In particular, we achieve tightness with respect to (n,k,r,ε) (upto log factors) across all regimes.

Short Bio: Gunjan Kumar is currently an Assistant Professor at IIT Kanpur. He completed his PhD at the Tata Institute of Fundamental Research (TIFR), Mumbai, and subsequently held a postdoctoral position at the School of Computing, National University of Singapore. His research interests include sublinear algorithms, property testing, and statistical estimation problems in small-sample regimes.