9 papers
Testing Sparse Functions over the Reals
Vipul Arora, Arnab Bhattacharyya, Philips George John +1
Over the last three decades, function testing has been extensively studied over Boolean, finite fields, and discrete settings. However, to encode the real-world applications more s…
Product distribution learning with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
Given i.i.d.~samples from an unknown distribution , the goal of distribution learning is to recover the parameters of a distribution that is close to . When belongs to th…
Algorithms and Hardness for Estimating Statistical Similarity
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions and over a finite sample space,…
Learning High-dimensional Gaussians from Censored Data
Arnab Bhattacharyya, Constantinos Daskalakis, Themis Gouleakis +1
We provide efficient algorithms for the problem of distribution learning from high-dimensional Gaussian data where in each sample, some of the variable values are missing. We suppo…
Approximating the Total Variation Distance between Gaussians
Arnab Bhattacharyya, Weiming Feng, Piyush Srivastava
The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it algorithmically ap…
Learning multivariate Gaussians with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is…