16 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…
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…
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,…
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm…
Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
Philips George John, Arnab Bhattacharyya, Silviu Maniu +2
Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomi…
Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set
Davin Choo, Chandler Squires, Arnab Bhattacharyya +1
Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments,…
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…
Learnability of Parameter-Bounded Bayes Nets
Arnab Bhattacharyya, Davin Choo, Sutanu Gayen +1
Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal p…
Online bipartite matching with imperfect advice
Davin Choo, Themis Gouleakis, Chun Kai Ling +1
We study the problem of online unweighted bipartite matching with offline vertices and online vertices where one wishes to be competitive against the optimal offline algori…
Outlier Robust Multivariate Polynomial Regression
Vipul Arora, Arnab Bhattacharyya, Mathews Boban +2
We study the problem of robust multivariate polynomial regression: let be an unknown -variate polynomial of degree at most in each variabl…
Optimal estimation of Gaussian (poly)trees
Yuhao Wang, Ming Gao, Wai Ming Tai +2
We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL dista…
Learning bounded-degree polytrees with known skeleton
Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya +1
We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesi…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
Improved Approximation for the Directed Spanner Problem
Arnab Bhattacharyya, Konstantin Makarychev
We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improv…