9 citations · 10 across the 4 of their papers we have counts for
10 papers · 1 filter
Support Size Estimation: The Power of Conditioning
Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel
We consider the problem of estimating the support size of a distribution . Our investigations are pursued through the lens of distribution testing and seek to understand the pow…
Pairwise Reachability Oracles and Preservers under Failures
Diptarka Chakraborty, Kushagra Chatterjee, Keerti Choudhary
In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let be a directed graph on -no…
Approximate Trace Reconstruction via Median String (in Average-Case)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
We consider an \emph{approximate} version of the trace reconstruction problem, where the goal is to recover an unknown string from traces (each trace is generat…
Approximating the Median under the Ulam Metric
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
We study approximation algorithms for variants of the \emph{median string} problem, which asks for a string that minimizes the sum of edit distances from a given set of strings…
New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures
Diptarka Chakraborty, Keerti Choudhary
In this paper, we consider the question of computing sparse subgraphs for any input directed graph on vertices and edges, that preserves reachability and/or stron…
Approximate Online Pattern Matching in Sub-linear Time
Diptarka Chakraborty, Debarati Das, Michal Koucky
We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern of length and a text of length over some alphabet $…