Debarati Das

According to our database, Debarati Das authored at least 25 papers between 2014 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2023

A Linear-Time <i>n</i>^0.4-Approximation for Longest Common Subsequence.

Karl Bringmann, Vincent Cohen-Addad, Debarati Das

ACM Trans. Algorithms, January, 2023

Weighted Edit Distance Computation: Strings, Trees, and Dyck.

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Clustering Permutations: New Techniques with Streaming Applications.

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing.

Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup

Proc. VLDB Endow., 2022

A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.

Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs.

Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding.

Debarati Das, Tomasz Kociumaka, Barna Saha

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Approximating LCS and Alignment Distance over Multiple Sequences.

Debarati Das, Barna Saha

Proceedings of the Approximation, 2022

2021

A Linear-Time n^0.4-Approximation for Longest Common Subsequence.

Karl Bringmann, Vincent Cohen-Addad, Debarati Das

CoRR, 2021

Approximating the Median under the Ulam Metric.

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Linear-Time n^0.4-Approximation for Longest Common Subsequence.

Karl Bringmann, Debarati Das

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Approximate Trace Reconstruction via Median String (In Average-Case).

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor.

Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks

J. ACM, 2020

No Repetition: Fast Streaming with Highly Concentrated Hashing.

Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup

CoRR, 2020

2019

Approximate Online Pattern Matching in Sublinear Time.

Diptarka Chakraborty, Debarati Das, Michal Koucký

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

Approximate Online Pattern Matching in Sub-linear Time.

Diptarka Chakraborty, Debarati Das, Michal Koucký

CoRR, 2018

Sparse Weight Tolerant Subgraph for Single Source Shortest Path.

Diptarka Chakraborty, Debarati Das

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.

Debarati Das, Michal Koucký, Michael E. Saks

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity.

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Optimal Quasi-Gray Codes: Does the Alphabet Matter?

Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

CoRR, 2017

Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path.

Diptarka Chakraborty, Debarati Das

CoRR, 2017

Dimension, pseudorandomness and extraction of pseudorandomness.

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Comput., 2017

2014

Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness.

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Electron. Colloquium Comput. Complex., 2014