Diptarka Chakraborty
Diptarka Chakraborty
Verified email at comp.nus.edu.sg - Homepage
TitleCited byYear
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
332016
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
212014
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
112018
Approximating edit distance within constant factor in truly sub-quadratic time
D Chakraborty, D Das, E Goldenberg, M Koucky, M Saks
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018
92018
Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks. Approximating edit distance within constant factor in truly sub-quadratic time
D Chakraborty
Proceedings of the 59th Annual Symposium on Foundations of Computer Science …, 2018
92018
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
92017
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
92017
Streaming algorithms for computing edit distance without exploiting suffix trees
D Chakraborty, E Goldenberg, M Koucký
arXiv preprint arXiv:1607.03718, 2016
82016
Low Distortion Embedding from Edit to Hamming Distance using Coupling.
D Chakraborty, E Goldenberg, M Koucký
Electronic Colloquium on Computational Complexity (ECCC) 22 (111), 4, 2015
62015
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
22015
Sparse Weight Tolerant Subgraph for Single Source Shortest Path
D Chakraborty, D Das
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), 2018
12018
Near optimal sized weight tolerant subgraph for single source shortest path
D Chakraborty, D Das
arXiv preprint arXiv:1707.04867, 2017
12017
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
12017
Dimension, pseudorandomness and extraction of pseudorandomness 1
M Agrawal, D Chakraborty, D Das, S Nandakumar
Computability 6 (3), 277-305, 2017
12017
Simultaneous time-space upper bounds for certain problems in planar graphs
D Chakraborty, R Tewari
arXiv preprint arXiv:1502.02135, 2015
12015
Approximate Online Pattern Matching in Sub-linear Time
D Chakraborty, D Das, M Koucky
arXiv preprint arXiv:1810.03551, 2018
2018
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
2018
1 Computing Edit Distance
D Chakraborty
2017
Optimal Quasi-Gray Codes: Does the Alphabet Matter?
D Chakraborty, D Das, M Koucký, N Saurabh
arXiv preprint arXiv:1712.01834, 2017
2017
Optimal Quasi-Gray Codes: The Alphabet Matters
D Chakraborty, D Das, M Koucký, N Saurabh
arXiv preprint arXiv:1712.01834, 2017
2017
The system can't perform the operation now. Try again later.
Articles 1–20