Diptarka Chakraborty
Diptarka Chakraborty
Verified email at comp.nus.edu.sg - Homepage
Title
Cited by
Cited by
Year
Streaming algorithms for embedding and computing edit distance in the low distance regime
D Chakraborty, E Goldenberg, M Koucký
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
612016
Approximating edit distance within constant factor in truly sub-quadratic time
D Chakraborty, D Das, E Goldenberg, M Koucký, M Saks
Journal of the ACM (JACM) 67 (6), 1-22, 2020
602020
New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs
D Chakraborty, A Pavan, R Tewari, NV Vinodchandran, LF Yang
34th International Conference on Foundation of Software Technology and …, 2014
272014
Tight cell probe bounds for succinct boolean matrix-vector multiplication
D Chakraborty, L Kamma, KG Larsen
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018
182018
An O (nϵ) space and polynomial time algorithm for reachability in directed layered planar graphs
D Chakraborty, R Tewari
ACM Transactions on Computation Theory (TOCT) 9 (4), 19, 2015
132015
Streaming algorithms for computing edit distance without exploiting suffix trees
D Chakraborty, E Goldenberg, M Koucký
arXiv preprint arXiv:1607.03718, 2016
122016
Low Distortion Embedding from Edit to Hamming Distance using Coupling.
D Chakraborty, E Goldenberg, M Koucký
Electron. Colloquium Comput. Complex. 22, 111, 2015
112015
New extremal bounds for reachability and strong-connectivity preservers under failures
D Chakraborty, K Choudhary
arXiv preprint arXiv:2004.12890, 2020
72020
Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks. 2018. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
D Chakraborty
FOCS. IEEE, 979-990, 0
6
Approximating the median under the Ulam metric
D Chakraborty, D Das, R Krauthgamer
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
52021
Approximate online pattern matching in sub-linear time
D Chakraborty, D Das, M Koucky
arXiv preprint arXiv:1810.03551, 2018
52018
Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E
D Chakraborty
distance within constant factor in truly subquadratic time. CoRR, abs/1810.03664, 2018
52018
Sparse weight tolerant subgraph for single source shortest path
D Chakraborty, D Das
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 2018
32018
Simultaneous time-space upper bounds for red-blue path problem in planar DAGs
D Chakraborty, R Tewari
International Workshop on Algorithms and Computation, 258-269, 2015
32015
An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
D Chakraborty, R Tewari
ACM Transactions on Computation Theory (TOCT) 9 (4), 1-11, 2017
22017
An O(nε) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
D Chakraborty, R Tewari
ACM Transactions on Computation Theory (TOCT) 9 (4), 1-11, 2017
22017
On Resource-bounded versions of the van Lambalgen theorem
D Chakraborty, S Nandakumar, H Shukla
International Conference on Theory and Applications of Models of Computation …, 2017
22017
Simultaneous time-space upper bounds for certain problems in planar graphs
D Chakraborty, R Tewari
arXiv preprint arXiv:1502.02135, 2015
22015
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity
D Chakraborty, D Das, M Koucký, N Saurabh
26th Annual European Symposium on Algorithms (ESA 2018), 2018
12018
Optimal Quasi-Gray Codes: Does the Alphabet Matter?
D Chakraborty, D Das, M Koucký, N Saurabh
arXiv preprint arXiv:1712.01834, 2017
12017
The system can't perform the operation now. Try again later.
Articles 1–20