Debarati Das

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 40

Top Topics

Pattern Matching

Distance Computation

Top Venues

Publications

Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. J. ACM 71 (2) (2024)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC. SPAA (2024)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. ACM Trans. Algorithms 19 (1) (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees, and Dyck. STOC (2023)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. ITCS (2023)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha
Weighted Edit Distance Computation: Strings, Trees and Dyck. CoRR (2023)
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. SODA (2022)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. ICALP (2022)
Debarati Das, Barna Saha
Approximating LCS and Alignment Distance over Multiple Sequences. APPROX/RANDOM (2022)
Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup
No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing. Proc. VLDB Endow. 15 (13) (2022)
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. SOSA (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. FOCS (2022)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS (2022)
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. CoRR (2022)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. CoRR (2022)
Karl Bringmann, Vincent Cohen-Addad, Debarati Das
-Approximation for Longest Common Subsequence. CoRR (2021)
Debarati Das, Barna Saha
Approximating LCS and Alignment Distance over Multiple Sequences. CoRR (2021)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. CoRR (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (In Average-Case). FSTTCS (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. SODA (2021)
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. FOCS (2021)
Karl Bringmann, Debarati Das
-Approximation for Longest Common Subsequence. ICALP (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (in Average-Case). CoRR (2021)
Debarati Das, Tomasz Kociumaka, Barna Saha
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. CoRR (2021)
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. CoRR (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. CoRR (2020)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67 (6) (2020)
Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup
No Repetition: Fast Streaming with Highly Concentrated Hashing. CoRR (2020)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sublinear Time. FSTTCS (2019)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS (2018)
Diptarka Chakraborty, Debarati Das
Sparse Weight Tolerant Subgraph for Single Source Shortest Path. SWAT (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký
Approximate Online Pattern Matching in Sub-linear Time. CoRR (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR (2018)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity. ESA (2018)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS (2018)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Dimension, pseudorandomness and extraction of pseudorandomness. Comput. 6 (3) (2017)
Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh
Optimal Quasi-Gray Codes: Does the Alphabet Matter? CoRR (2017)
Diptarka Chakraborty, Debarati Das
Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path. CoRR (2017)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Dimension, Pseudorandomness and Extraction of Pseudorandomness. FSTTCS (2015)
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar
Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness. Electron. Colloquium Comput. Complex. 21 (2014)