Publications

•  A Generic Framework for Fair Consensus Clustering in Streams

         joint work with Diptarka Chakraborty, Kushagra Chatterjee, and Tien Long Nguyen.

        AAMAS 2026 (Oral Presentation)

•  Generalizing Fair Clustering to Multiple Groups: Algorithms and Applications

         joint work with Diptarka Chakraborty, Kushagra Chatterjee, and Tien Long Nguyen.

        AAAI 2026 (Oral Presentation)

•  Tree Violation Distance under Constraints

        joint work with Evangelos Kipouridis, and Joachim Spoerhase.

        SOSA 2026

•  Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance

        joint work with Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha.

        FOCS 2025

•  Towards Fair Representation: Clustering and Consensus

        joint work with Diptarka Chakraborty, Kushagra Chatterjee, Tien Long Nguyen, and Romina Nobahari.

       COLT 2025

•  Fitting Tree Metrics and Ultrametrics in Data Streams

      joint work with Amir Carmel, Evangelos Kipouridis, and Evangelos Pipis.

       ICALP 2025

• Breaking the Two Approximation Barrier for Various Consensus Clustering Problems

        joint work with Amit Kumar.

       SODA 2025

• Upper and Lower Bounds for Edit Distance in Space-Efficient MPC

        joint work with Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha.

       SPAA 2024 (brief  announcement)

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

        joint work with Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha.

       STOC 2023

• Clustering Permutations: New Techniques with Streaming Applications

        joint work Diptarka Chakraborty, and Robert Krauthgamer.

       ITCS 2023

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

        joint work with Anders Aamand, Evangelos Kipouridis, Jakob Bk Tejs Knudsen, Peter M. R. Rasmussen, and Mikkel Thorup. 

       VLDB 2022

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

        joint work with Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, and Hamed Saleh. 

       FOCS 2022

• Approximating LCS and Alignment Distance over Multiple Sequences

       joint work with Barna Saha.

      APPROX 2022

•  Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding

       joint work with Tomasz Kociumaka, and Barna Saha. 

      ICALP 22

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

       joint work with Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. 

       SODA 22

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

       joint work with Evangelos Kipouridis, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. 

      SOSA 22

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

       joint work with Vincent Cohen-Addad, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup.

      FOCS 21

• Approximate Trace Reconstruction via Median String (in Average-Case)

      joint work with Diptarka Chakraborty, and Robert Krauthgamer.

     FSTTCS 21

•  An n0.4-Approximation to Longest Common Subsequence in Linear Time with High Probability

      joint work with Karl Bringmann.

     ICALP 21

•  Approximating the Median under the Ulam Metric

     joint work with Diptarka Chakraborty, and Robert Krauthgamer. 

    SODA 21

• Approximate Online Pattern Matching in Sub-linear Time

      joint work with Diptarka Chakraborty, and Michal Koucky. 

      FSTTCS 19

•  Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

       joint work with Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky, and Michael Saks. (Best paper)

       FOCS 18

       Also published in Journal of the ACM (J. ACM), Volume 67(6): 36:1-36:22 (2020)

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

      joint work with Diptarka Chakraborty, Michal Koucky, and Nitin Saurabh.

      ESA 18

•  Sparse Weight Tolerant Subgraph for Single Source Shortest Path

      joint work with Diptarka Chakraborty.

      SWAT 18

•  Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication

      joint work with Michal Koucky, and Michael Saks.

      STACS 18

• Dimension, Pseudorandomness and Extraction of Pseudorandomness

     joint work with Manindra Agrawal, Diptarka Chakraborty, and Satyadev Nandakumar.

     FSTTCS 15

     Also Published in Computability - The Journal of the Association Computability in Europe 6(3): 277-305 (2017).