16 citations · 42 across the 21 of their papers we have counts for
23 papers
Estimating Size of the Union of Sets in Streaming Model
Kuldeep S. Meel, N. V. Vinodchandran, Sourav Chakraborty
We study estimating the size of the union of sets , where each is presented implicitly and arrives in a stream. We introduce Delphic sets, a class of…
Fast Rational Search via Stern-Brocot Tree
Connor Weyers, N. V. Vinodchandran
We revisit the problem of rational search: given an unknown rational number with , the goal is to identify using comparison queries of the…
Point Prediction for Streaming Data
Aleena Chanda, N. V. Vinodchandran, Bertrand Clarke
We present two new approaches for point prediction with streaming data. One is based on the Count-Min sketch (CMS) and the other is based on Gaussian process priors with a random b…
Total Variation Distance for Product Distributions is -Complete
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We show that computing the total variation distance between two product distributions is -complete. This is in stark contrast with other distance measures such as Kul…
Distribution Learning Meets Graph Structure Sampling
Arnab Bhattacharyya, Sutanu Gayen, Philips George John +2
This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, usin…
Total Variation Distance Meets Probabilistic Inference
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-prese…
Neighborhood Variants of the KKM Lemma, Lebesgue Covering Theorem, and Sperner's Lemma on the Cube
Jason Vander Woude, Peter Dixon, A. Pavan +2
We establish a "neighborhood" variant of the cubical KKM lemma and the Lebesgue covering theorem and deduce a discretized version which is a "neighborhood" variant of Sperner's lem…
Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma
Jason Vander Woude, Peter Dixon, A. Pavan +2
A partition of is called a -secluded partition if, for every , the ball $\overline{B}_{\infty}(\varepsilon,…
List and Certificate Complexities in Replicable Learning
Peter Dixon, A. Pavan, Jason Vander Woude +1
We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe…
Constraint Optimization over Semirings
A. Pavan, Kuldeep S. Meel, N. V. Vinodchandran +1
Interpretations of logical formulas over semirings have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide…
Geometry of Rounding
Jason Vander Woude, Peter Dixon, A. Pavan +2
Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of are equivalent, we introduce the followi…
On Approximating Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV d…
Efficient inference of interventional distributions
Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy +2
We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let be a causal model…
Model Counting meets F0 Estimation
A. Pavan, N. V. Vinodchandran, Arnab Bhattacharyya +1
Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science…
Promise Problems Meet Pseudodeterminism
Peter Dixon, A. Pavan, N. V. Vinodchandran
The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation…
Testing Product Distributions: A Closer Look
Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy +1
We study the problems of identity and closeness testing of -dimensional product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis…
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price +1
We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a dist…
Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +1
We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems:…
Learning and Sampling of Atomic Interventions from Observations
Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy +2
We study the problem of efficiently estimating the effect of an intervention on a single variable (atomic interventions) using observational samples in a causal Bayesian network. O…
On optimal language compression for sets in PSPACE/poly
N. V. Vinodchandran, Marius Zimand
We show that if DTIME[2^O(n)] is not included in DSPACE[2^o(n)], then, for every set B in PSPACE/poly, all strings x in B of length n can be represented by a string compressed(x) o…
Resource-bounded Dimension in Computational Learning Theory
Ricard Gavalda, Maria Lopez-Valdes, Elvira Mayordomo +1
This paper focuses on the relation between computational learning theory and resource-bounded dimension. We intend to establish close connections between the learnability/nonlearna…
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Samir Datta, Raghav Kulkarni, Raghunath Tewari +1
We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that t…
On the Power of Unambiguity in Logspace
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\Reach…