Diptarka Chakraborty

activity

20152026

most citedStreaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees

9 citations · 18 across the 22 of their papers we have counts for

collaborators

Showing 2021Show all

2 papers · 1 filter

cs.DS2021

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 $G = (V, E)$ be a directed graph on $n$ -no…

cs.DS2021

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 $s \in {0, 1}^{n}$ from $m$ traces (each trace is generat…