Search Results

Documents authored by Dey, Sanjana

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.32
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric

Authors: Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., and Michal Koucký

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
A function φ: {0,1}^n → {0,1}^N is called an isometric embedding of the n-dimensional Hamming metric space to the N-dimensional edit metric space if, for all x, y ∈ {0,1}ⁿ, the Hamming distance between x and y is equal to the edit distance between φ(x) and φ(y). The rate of such an embedding is defined as the ratio n/N. It is well known in the literature how to construct isometric embeddings with a rate of Ω(1/log n). However, achieving even near-isometric embeddings with a positive constant rate has remained elusive until now. In this paper, we present an isometric embedding with a rate of 1/8 by discovering connections to synchronization strings, which were studied in the context of insertion-deletion codes (Haeupler-Shahrasbi [JACM'21]). At a technical level, we introduce a framework for obtaining high-rate isometric embeddings using a novel object called a misaligner. We speculate that, with sufficient computational resources, our framework could potentially yield isometric embeddings with a rate of 1/5. As an immediate consequence of our constant rate isometric embedding, we improve known conditional lower bounds for the closest pair problem and the discrete 1-center problem in the edit metric and NP-hardness of approximation results for clustering problems and the Steiner tree problem in the edit metric, but now with optimal dependency on the dimension. Furthermore, we obtain optimal lower bounds for the gap edit distance problem in the two-player randomized communication complexity model. We complement our results by showing that no isometric embedding φ:{0,1}^n → {0,1}^N can have rate greater than 15/32 for all positive integers n. En route to proving this upper bound, we uncover fundamental structural properties necessary for every Hamming-to-edit isometric embedding. We also prove similar upper and lower bounds for embeddings over larger alphabets. Finally, we consider embeddings φ:Σ_in^n → Σ_out^N between different input and output alphabets, where the rate is given by (n log|Σ_in|)/(Nlog|Σ_out|). In this setting, we show that the rate can be made arbitrarily close to 1.
Cite as

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., and Michal Koucký. Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ICALP.2026.32,
  author =	{Bhattacharya, Sudatta and Dey, Sanjana and Goldenberg, Elazar and Habib, Mursalin and Haeupler, Bernhard and Karthik C. S. and Kouck\'{y}, Michal},
  title =	{{Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.32},
  URN =		{urn:nbn:de:0030-drops-264215},
  doi =		{10.4230/LIPIcs.ICALP.2026.32},
  annote =	{Keywords: Edit distance, Hamming distance, metric embeddings, synchronization strings, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.11
Many Flavors of Edit Distance

Authors: Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, and Michal Koucký

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and substitutions required to transform one string into another, while the latter specifically quantifies the number of insertions and deletions. Many algorithmic solutions explicitly address one of these measures, and frequently techniques applicable to one can also be adapted to work with the other. In this paper, we investigate whether there exists a standardized approach for applying results from one setting to another. Specifically, we demonstrate the capability to reduce questions regarding string similarity over arbitrary alphabets to equivalent questions over a binary alphabet. Furthermore, we illustrate how to transform questions concerning indel distance into equivalent questions based on edit distance. This complements an earlier result of Tiskin (2007) which addresses the inverse direction.
Cite as

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, and Michal Koucký. Many Flavors of Edit Distance. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.FSTTCS.2024.11,
  author =	{Bhattacharya, Sudatta and Dey, Sanjana and Goldenberg, Elazar and Kouck\'{y}, Michal},
  title =	{{Many Flavors of Edit Distance}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.11},
  URN =		{urn:nbn:de:0030-drops-222004},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.11},
  annote =	{Keywords: Edit distance, Indel distance, Embedding, LCS, Alphabet Reduction}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.17
Matrix Completion: Approximating the Minimum Diameter

Authors: Diptarka Chakraborty and Sanjana Dey

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
In this paper, we focus on the matrix completion problem and aim to minimize the diameter over an arbitrary alphabet. Given a matrix M with missing entries, our objective is to complete the matrix by filling in the missing entries in a way that minimizes the maximum (Hamming) distance between any pair of rows in the completed matrix (also known as the diameter of the matrix). It is worth noting that this problem is already known to be NP-hard. Currently, the best-known upper bound is a 4-approximation algorithm derived by applying the triangle inequality together with a well-known 2-approximation algorithm for the radius minimization variant. In this work, we make the following contributions: - We present a novel 3-approximation algorithm for the diameter minimization variant of the matrix completion problem. To the best of our knowledge, this is the first approximation result that breaks below the straightforward 4-factor bound. - Furthermore, we establish that the diameter minimization variant of the matrix completion problem is (2-ε)-inapproximable, for any ε > 0, even when considering a binary alphabet, under the assumption that 𝖯 ≠ NP. This is the first result that demonstrates a hardness of approximation for this problem.
Cite as

Diptarka Chakraborty and Sanjana Dey. Matrix Completion: Approximating the Minimum Diameter. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2023.17,
  author =	{Chakraborty, Diptarka and Dey, Sanjana},
  title =	{{Matrix Completion: Approximating the Minimum Diameter}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.17},
  URN =		{urn:nbn:de:0030-drops-193197},
  doi =		{10.4230/LIPIcs.ISAAC.2023.17},
  annote =	{Keywords: Incomplete Data, Matrix Completion, Hamming Distance, Diameter Minimization, Approximation Algorithms, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.24
Discriminating Codes in Geometric Setups

Authors: Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study two geometric variations of the discriminating code problem. In the discrete version, a finite set of points P and a finite set of objects S are given in ℝ^d. The objective is to choose a subset S^* ⊆ S of minimum cardinality such that the subsets S_i^* ⊆ S^* covering p_i, satisfy S_i^* ≠ ∅ for each i = 1,2,…, n, and S_i^* ≠ S_j^* for each pair (i,j), i ≠ j. In the continuous version, the solution set S^* can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case (d = 1), the points are placed on some fixed-line L, and the objects in S are finite segments of L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in 1D. We then design a polynomial-time 2-approximation algorithm for the 1-dimensional discrete case. We also design a PTAS for both discrete and continuous cases when the intervals are all required to have the same length. We then study the 2-dimensional case (d = 2) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-hard, and design polynomial-time approximation algorithms with factors 4+ε and 32+ε, respectively (for every fixed ε > 0).
Cite as

Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen. Discriminating Codes in Geometric Setups. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2020.24,
  author =	{Dey, Sanjana and Foucaud, Florent and Nandy, Subhas C. and Sen, Arunabha},
  title =	{{Discriminating Codes in Geometric Setups}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.24},
  URN =		{urn:nbn:de:0030-drops-133686},
  doi =		{10.4230/LIPIcs.ISAAC.2020.24},
  annote =	{Keywords: Discriminating code, Approximation algorithm, Segment stabbing, Geometric Hitting set}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact