16 citations · 42 across the 21 of their papers we have counts for
7 papers · 1 filter
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…
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,…
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…
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…