9 citations · 10 across the 4 of their papers we have counts for
4 papers
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen
The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems,…
Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path
Diptarka Chakraborty, Debarati Das
In this paper we address the problem of computing a sparse subgraph of a weighted directed graph such that the exact distances from a designated source vertex to all other vertices…
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required t…
Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs
Diptarka Chakraborty, Raghunath Tewari
In this paper, we show that given a weighted, directed planar graph , and any , there exists a polynomial time and space algorithm that computes the…