16 citations · 25 across the 14 of their papers we have counts for
15 papers
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…
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…
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…
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…
Measuring the Impact of Influence on Individuals: Roadmap to Quantifying Attitude
Xiaoyun Fu, Madhavan Rajagopal Padmanabhan, Raj Gaurav Kumar +3
Influence diffusion has been central to the study of propagation of information in social networks, where influence is typically modeled as a binary property of entities: influence…
Parallel Triangle Counting in Massive Streaming Graphs
Kanat Tangwongsan, A. Pavan, Srikanta Tirthapura
The number of triangles in a graph is a fundamental metric, used in social network analysis, link classification and recommendation, and more. Driven by these applications and the…
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
Xiaoyang Gu, John M. Hitchcock, A. Pavan
This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one…
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…