23 Search Results for "Chakraborty, Diptarka"

Document
DOI: 10.4230/LIPIcs.ESA.2025.68
Faster Algorithm for Second (s,t)-Mincut and Breaking Quadratic Barrier for Dual Edge Sensitivity for (s,t)-Mincut

Authors: Surender Baswana, Koustav Bhanja, and Anupam Roy

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Let G be a directed graph on n vertices and m edges. In this article, we study (s,t)-cuts of second minimum capacity and present the following algorithmic and graph-theoretic results. 1) Second (s,t)-mincut: Vazirani and Yannakakis [ICALP 1992] designed the first algorithm for computing an (s,t)-cut of second minimum capacity using {O}(n²) maximum (s,t)-flow computations. We present the following algorithm that improves the running time significantly. For directed integer-weighted graphs, there is an algorithm that can compute an (s,t)-cut of second minimum capacity using Õ(√n) maximum (s,t)-flow computations with high probability. To achieve this result, a close relationship of independent interest is established between (s,t)-cuts of second minimum capacity and global mincuts in directed weighted graphs. 2) Minimum+1 (s,t)-cuts: Minimum+1 (s,t)-cuts have been studied quite well recently [Baswana, Bhanja, and Pandey, ICALP 2022 & TALG 2023], which is a special case of second (s,t)-mincut. We present the following structural result and the first nontrivial algorithm for minimum+1 (s,t)-cuts. 3) Algorithm: For directed multi-graphs, we design an algorithm that, given any maximum (s,t)-flow, computes a minimum+1 (s,t)-cut, if it exists, in O(m) time. 4) Structure: The existing structures for storing and characterizing all minimum+1 (s,t)-cuts occupy {O}(mn) space [Baswana, Bhanja, and Pandey, TALG 2023]. For undirected multi-graphs, we design a directed acyclic graph (DAG) occupying only {O}(m) space that stores and characterizes all minimum+1 (s,t)-cuts. This matches the space bound of the widely-known DAG structure for all (s,t)-mincuts [Picard and Queyranne, Math. Prog. Studies 1980]. 5) Dual Edge Sensitivity Oracle: The study of minimum+1 (s,t)-cuts often turns out to be useful in designing dual edge sensitivity oracles - a compact data structure for efficiently reporting an (s,t)-mincut after insertion/failure of any given pair of query edges. It has been shown recently [Bhanja, ICALP 2025] that any dual edge sensitivity oracle for (s,t)-mincut in undirected multi-graphs must occupy Ω(n²) space in the worst-case irrespective of the query time. Interestingly, for undirected unweighted simple graphs, we break this quadratic barrier while achieving a non-trivial query time as follows. There is an O(n√n) space data structure that can report an (s,t)-mincut in O(min{m,n√n}) time after the insertion/failure of any given pair of query edges. To arrive at our results, as one of our key techniques, we establish interesting relationships between (s,t)-cuts of capacity (minimum+Δ), Δ ≥ 0, and maximum (s,t)-flow. We believe that these techniques and the graph-theoretic result in 2.(b) are of independent interest.
Cite as

Surender Baswana, Koustav Bhanja, and Anupam Roy. Faster Algorithm for Second (s,t)-Mincut and Breaking Quadratic Barrier for Dual Edge Sensitivity for (s,t)-Mincut. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 68:1-68:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ESA.2025.68,
  author =	{Baswana, Surender and Bhanja, Koustav and Roy, Anupam},
  title =	{{Faster Algorithm for Second (s,t)-Mincut and Breaking Quadratic Barrier for Dual Edge Sensitivity for (s,t)-Mincut}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{68:1--68:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.68},
  URN =		{urn:nbn:de:0030-drops-245369},
  doi =		{10.4230/LIPIcs.ESA.2025.68},
  annote =	{Keywords: mincut, second mincut, compact structure, fault tolerant, sensitivity oracle, dual edges, st mincut, global mincut, characterization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.111
Hardness of Median and Center in the Ulam Metric

Authors: Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The classical rank aggregation problem seeks to combine a set X of n permutations into a single representative "consensus" permutation. In this paper, we investigate two fundamental rank aggregation tasks under the well-studied Ulam metric: computing a median permutation (which minimizes the sum of Ulam distances to X) and computing a center permutation (which minimizes the maximum Ulam distance to X) in two settings. - Continuous Setting: In the continuous setting, the median/center is allowed to be any permutation. It is known that computing a center in the Ulam metric is NP-hard and we add to this by showing that computing a median is NP-hard as well via a simple reduction from the Max-Cut problem. While this result may not be unexpected, it had remained elusive until now and confirms a speculation by Chakraborty, Das, and Krauthgamer [SODA '21]. - Discrete Setting: In the discrete setting, the median/center must be a permutation from the input set. We fully resolve the fine-grained complexity of the discrete median and discrete center problems under the Ulam metric, proving that the naive Õ(n² L)-time algorithm (where L is the length of the permutation) is conditionally optimal. This resolves an open problem raised by Abboud, Bateni, Cohen-Addad, Karthik C. S., and Seddighin [APPROX '23]. Our reductions are inspired by the known fine-grained lower bounds for similarity measures, but we face and overcome several new highly technical challenges.
Cite as

Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S.. Hardness of Median and Center in the Ulam Metric. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 111:1-111:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ESA.2025.111,
  author =	{Fischer, Nick and Goldenberg, Elazar and Habib, Mursalin and Karthik C. S.},
  title =	{{Hardness of Median and Center in the Ulam Metric}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{111:1--111:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.111},
  URN =		{urn:nbn:de:0030-drops-245809},
  doi =		{10.4230/LIPIcs.ESA.2025.111},
  annote =	{Keywords: Ulam distance, median, center, rank aggregation, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.7
Sequence Similarity Estimation by Random Subsequence Sketching

Authors: Ke Chen, Vinamratha Pattar, and Mingfu Shao

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Sequence similarity estimation is essential for many bioinformatics tasks, including functional annotation, phylogenetic analysis, and overlap graph construction. Alignment-free methods aim to solve large-scale sequence similarity estimation by mapping sequences to more easily comparable features that can approximate edit distances efficiently. Substrings or k-mers, as the dominant choice of features, face an unavoidable compromise between sensitivity and specificity when selecting the proper k-value. Recently, subsequence-based features have shown improved performance, but they are computationally demanding, and determining the ideal subsequence length remains an intricate art. In this work, we introduce SubseqSketch, a novel alignment-free scheme that maps a sequence to an integer vector, where the entries correspond to dynamic, rather than fixed, lengths of random subsequences. The cosine similarity between these vectors exhibits a strong correlation with the edit similarity between the original sequences. Through experiments on benchmark datasets, we demonstrate that SubseqSketch is both efficient and effective across various alignment-free tasks, including nearest neighbor search and phylogenetic clustering. A C++ implementation of SubseqSketch is openly available at https://github.com/Shao-Group/SubseqSketch.
Cite as

Ke Chen, Vinamratha Pattar, and Mingfu Shao. Sequence Similarity Estimation by Random Subsequence Sketching. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.WABI.2025.7,
  author =	{Chen, Ke and Pattar, Vinamratha and Shao, Mingfu},
  title =	{{Sequence Similarity Estimation by Random Subsequence Sketching}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.7},
  URN =		{urn:nbn:de:0030-drops-239332},
  doi =		{10.4230/LIPIcs.WABI.2025.7},
  annote =	{Keywords: Alignment-free sequence comparison, Phylogenetic clustering, Nearest neighbor search, Edit distance embedding}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.110
An Optimal 3-Fault-Tolerant Connectivity Oracle

Authors: Evangelos Kosinas

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present an optimal oracle for answering connectivity queries in undirected graphs in the presence of at most three vertex failures. Specifically, we show that we can process a graph G in O(n+m) time, in order to build a data structure that occupies O(n) space, which can be used in order to answer queries of the form "given a set F of at most three vertices, and two vertices x and y not in F, are x and y connected in G⧵ F?" in constant time, where n and m denote the number of vertices and edges, respectively, of G. The idea is to rely on the DFS-based framework introduced by Kosinas [ESA'23], for handling connectivity queries in the presence of multiple vertex failures. Our technical contribution is to show how to appropriately extend the toolkit of the DFS-based parameters, in order to optimally handle up to three vertex failures. Our approach has the interesting property that it does not rely on a compact representation of vertex cuts, and has the potential to provide optimal solutions for more vertex failures. Furthermore, we show that the DFS-based framework can be easily extended in order to answer vertex-cut queries, and the number of connected components in the presence of multiple vertex failures. In the case of three vertex failures, we can answer such queries in O(log n) time.
Cite as

Evangelos Kosinas. An Optimal 3-Fault-Tolerant Connectivity Oracle. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 110:1-110:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kosinas:LIPIcs.ICALP.2025.110,
  author =	{Kosinas, Evangelos},
  title =	{{An Optimal 3-Fault-Tolerant Connectivity Oracle}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{110:1--110:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.110},
  URN =		{urn:nbn:de:0030-drops-234879},
  doi =		{10.4230/LIPIcs.ICALP.2025.110},
  annote =	{Keywords: Graphs, Connectivity, Fault-Tolerant, Oracles}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.3
Near-Optimal Trace Reconstruction for Mildly Separated Strings

Authors: Anders Aamand, Allen Liu, and Shyam Narayanan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In the trace reconstruction problem our goal is to learn an unknown string x ∈ {0,1}ⁿ given independent traces of x. A trace is obtained by independently deleting each bit of x with some probability δ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability δ is constant. The best known upper bound and lower bounds are respectively exp(Õ(n^{1/5})) [Zachary Chase, 2021a] and ̃ Ω(n^{3/2}) [Zachary Chase, 2021b]. Our main result is that if the string x is mildly separated, meaning that the number of zeros between any two ones in x is at least polylog n, and if δ is a sufficiently small constant, then the trace reconstruction problem can be solved with O(n log n) traces and in polynomial time.
Cite as

Anders Aamand, Allen Liu, and Shyam Narayanan. Near-Optimal Trace Reconstruction for Mildly Separated Strings. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.ICALP.2025.3,
  author =	{Aamand, Anders and Liu, Allen and Narayanan, Shyam},
  title =	{{Near-Optimal Trace Reconstruction for Mildly Separated Strings}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.3},
  URN =		{urn:nbn:de:0030-drops-233801},
  doi =		{10.4230/LIPIcs.ICALP.2025.3},
  annote =	{Keywords: Trace Reconstruction, deletion channel, sample complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.27
Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s,t)-cut

Authors: Koustav Bhanja

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Let G = (V,E) be an undirected multi-graph on n = |V| vertices and S ⊆ V be a Steiner set in G. Steiner cut is a fundamental concept; moreover, global cut (|S| = n), as well as (s,t)-cut (|S| = 2), is just a special case of Steiner cut. We study Steiner cuts of capacity minimum+1, and as an important application, we provide a dual edge Sensitivity Oracle for Steiner mincut - a compact data structure for efficiently reporting a Steiner mincut after failure/insertion of any pair of edges. A compact data structure for cuts of capacity minimum+1 has been designed for both global cuts [Dinitz and Nutov, STOC 1995] and (s,t)-cuts [Baswana, Bhanja, and Pandey, ICALP 2022 & TALG 2023]. Moreover, both data structures are also used crucially to design a dual edge Sensitivity Oracle for their respective mincuts. Unfortunately, except for these two extreme scenarios of Steiner cuts, no generalization of these results is known. Therefore, to address this gap, we present the following first results on Steiner cuts for any S satisfying 2 ≤ |S| ≤ n. 1) Data Structure for Minimum+1 Steiner Cut: There is an {O}(n(n-|S|+1)) space data structure that, given any pair of vertices u,v, can determine in {O}(1) time whether the Steiner cut of the least capacity separating u and v has capacity minimum+1. It can report such a cut, if it exists, in {O}(n) time, which is worst-case optimal. 2) Dual Edge Sensitivity Oracle: We design the following pair of data structures. (a) There is an {O}(n(n-|S|+1)) space data structure that, after the failure or insertion of any pair of edges in G, can report the capacity of Steiner mincut in {O}(1) time and a Steiner mincut in {O}(n) time, which is worst-case optimal. (b) If we are interested in reporting only the capacity of Steiner mincut, there is a more compact data structure that occupies {O}((n-|S|)²+n) space and can report the capacity of Steiner mincut in {O}(1) time after the failure or insertion of any pair of edges. 3) Lower Bound for Sensitivity Oracle: For undirected multi-graphs, for any Steiner set S ⊆ V, any data structure that, after the failure or insertion of any pair of edges, can report the capacity of Steiner mincut must occupy Ω((n-|S|)²) bits of space in the worst case, irrespective of the query time. To arrive at our results, we provide several techniques, especially a generalization of the 3-Star Lemma given by Dinitz and Vainshtein [SICOMP 2000], which is of independent interest. Our results achieve the same space and time bounds of the existing results for the two extreme scenarios of Steiner cuts - global and (s,t)-cut. In addition, the space occupied by our data structures in (1) and (2) reduces as |S| tends to n. Also, they occupy subquadratic space if |S| is close to n.
Cite as

Koustav Bhanja. Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s,t)-cut. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhanja:LIPIcs.ICALP.2025.27,
  author =	{Bhanja, Koustav},
  title =	{{Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s,t)-cut}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.27},
  URN =		{urn:nbn:de:0030-drops-234040},
  doi =		{10.4230/LIPIcs.ICALP.2025.27},
  annote =	{Keywords: cut, mincut, minimum+1, steiner, edge fault, sensitivity oracle, dual edges}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.100
Robust-Sorting and Applications to Ulam-Median

Authors: Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal when the outcome of each comparison is error-free. However, many real-world sorting applications operate in scenarios where the outcome of each comparison can be noisy. In this work, we explore settings where a bounded number of comparisons are potentially corrupted by erroneous agents, resulting in arbitrary, adversarial outcomes. We model the sorting problem as a query-limited tournament graph where edges involving erroneous nodes may yield arbitrary results. Our primary contribution is a randomized algorithm inspired by quick-sort that, in expectation, produces an ordering close to the true total order while only querying Õ(n) edges. We achieve a distance from the target order π within (3 + ε)|B|, where B is the set of erroneous nodes, balancing the competing objectives of minimizing both query complexity and misalignment with π. Our algorithm needs to carefully balance two aspects - identify a pivot that partitions the vertex set evenly and ensure that this partition is "truthful" and yet query as few "triangles" in the graph G as possible. Since the nodes in B can potentially hide in an intricate manner, our algorithm requires several technical steps that ensure that progress is made in each recursive step. Additionally, we demonstrate significant implications for the Ulam-k-Median problem. This is a classical clustering problem where the metric is defined on the set of permutations on a set of d elements. Chakraborty, Das, and Krauthgamer gave a (2-ε) FPT approximation algorithm for this problem, where the running time is super-linear in both n and d. We give the first (2-ε) FPT linear time approximation algorithm for this problem. Our main technical result gives a strengthening of the results in Chakraborty et al. by showing that a good 1-median solution can be obtained from a constant-size random sample of the input. We use our robust sorting framework to find a good solution from such a random sample. We feel that the notion of robust sorting should have applications in several such settings.
Cite as

Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-Sorting and Applications to Ulam-Median. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jaiswal_et_al:LIPIcs.ICALP.2025.100,
  author =	{Jaiswal, Ragesh and Kumar, Amit and Yadav, Jatin},
  title =	{{Robust-Sorting and Applications to Ulam-Median}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{100:1--100:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.100},
  URN =		{urn:nbn:de:0030-drops-234774},
  doi =		{10.4230/LIPIcs.ICALP.2025.100},
  annote =	{Keywords: Sorting, clustering, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.28
Coresets for 1-Center in 𝓁₁ Metrics

Authors: Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We explore the applicability of coresets - a small subset of the input dataset that approximates a predefined set of queries - to the 1-center problem in 𝓁₁ spaces. This approach could potentially extend to solving the 1-center problem in related metric spaces, and has implications for streaming and dynamic algorithms. We show that in 𝓁₁, unlike in Euclidean space, even weak coresets exhibit exponential dependency on the underlying dimension. Moreover, while inputs with a unique optimal center admit better bounds, they are not dimension independent. We then relax the guarantee of the coreset further, to merely approximate the value (optimal cost of 1-center), and obtain a dimension-independent coreset for every desired accuracy ε > 0. Finally, we discuss the broader implications of our findings to related metric spaces, and show explicit implications to Jaccard and Kendall’s tau distances.
Cite as

Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer. Coresets for 1-Center in 𝓁₁ Metrics. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.ITCS.2025.28,
  author =	{Carmel, Amir and Guo, Chengzhi and Jiang, Shaofeng H.-C. and Krauthgamer, Robert},
  title =	{{Coresets for 1-Center in 𝓁₁ Metrics}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.28},
  URN =		{urn:nbn:de:0030-drops-226566},
  doi =		{10.4230/LIPIcs.ITCS.2025.28},
  annote =	{Keywords: clustering, k-center, minimum enclosing balls, coresets, 𝓁₁ norm, Kendall’s tau, Jaccard metric}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.12
Approximate Maximum Rank Aggregation: Beyond the Worst-Case

Authors: Yan Hong Yao Alvin and Diptarka Chakraborty

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
The fundamental task of rank aggregation is to combine multiple rankings on a group of candidates into a single ranking to mitigate biases inherent in individual input rankings. This task has a myriad of applications, such as in social choice theory, collaborative filtering, web search, statistics, databases, sports, and admission systems. One popular version of this task, maximum rank aggregation (or the center ranking problem), aims to find a ranking (not necessarily from the input set) that minimizes the maximum distance to the input rankings. However, even for four input rankings, this problem is NP-hard (Dwork et al., WWW'01, and Biedl et al., Discrete Math.'09), and only a (folklore) polynomial-time 2-approximation algorithm is known for finding an optimal aggregate ranking under the commonly used Kendall-tau distance metric. Achieving a better approximation factor in polynomial time, ideally, a polynomial time approximation scheme (PTAS), is one of the major challenges. This paper presents significant progress in solving this problem by considering the Mallows model, a classical probabilistic model. Our proposed algorithm outputs an (1+ε)-approximate aggregate ranking for any ε > 0, with high probability, as long as the input rankings come from a Mallows model, even in a streaming fashion. Furthermore, the same approximation guarantee is achieved even in the presence of outliers, presumably a more challenging task.
Cite as

Yan Hong Yao Alvin and Diptarka Chakraborty. Approximate Maximum Rank Aggregation: Beyond the Worst-Case. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alvin_et_al:LIPIcs.FSTTCS.2023.12,
  author =	{Alvin, Yan Hong Yao and Chakraborty, Diptarka},
  title =	{{Approximate Maximum Rank Aggregation: Beyond the Worst-Case}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.12},
  URN =		{urn:nbn:de:0030-drops-193857},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.12},
  annote =	{Keywords: Rank Aggregation, Center Problem, Mallows Model, Approximation Algorithms, Clustering with Outliers}
}
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.MFCS.2023.33
Support Size Estimation: The Power of Conditioning

Authors: Diptarka Chakraborty, Gunjan Kumar, and Kuldeep S. Meel

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We consider the problem of estimating the support size of a distribution D. Our investigations are pursued through the lens of distribution testing and seek to understand the power of conditional sampling (denoted as COND), wherein one is allowed to query the given distribution conditioned on an arbitrary subset S. The primary contribution of this work is to introduce a new approach to lower bounds for the COND model that relies on using powerful tools from information theory and communication complexity. Our approach allows us to obtain surprisingly strong lower bounds for the COND model and its extensions. - We bridge the longstanding gap between the upper bound O(log log n + 1/ε²) and the lower bound Ω(√{log log n}) for the COND model by providing a nearly matching lower bound. Surprisingly, we show that even if we get to know the actual probabilities along with COND samples, still Ω(log log n + 1/{ε² log (1/ε)}) queries are necessary. - We obtain the first non-trivial lower bound for the COND equipped with an additional oracle that reveals the actual as well as the conditional probabilities of the samples (to the best of our knowledge, this subsumes all of the models previously studied): in particular, we demonstrate that Ω(log log log n + 1/{ε² log (1/ε)}) queries are necessary.
Cite as

Diptarka Chakraborty, Gunjan Kumar, and Kuldeep S. Meel. Support Size Estimation: The Power of Conditioning. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2023.33,
  author =	{Chakraborty, Diptarka and Kumar, Gunjan and Meel, Kuldeep S.},
  title =	{{Support Size Estimation: The Power of Conditioning}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.33},
  URN =		{urn:nbn:de:0030-drops-185675},
  doi =		{10.4230/LIPIcs.MFCS.2023.33},
  annote =	{Keywords: Support-size estimation, Distribution testing, Conditional sampling, Lower bound}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.123
Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?

Authors: Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Given a Boolean formula ϕ over n variables, the problem of model counting is to compute the number of solutions of ϕ. Model counting is a fundamental problem in computer science with wide-ranging applications in domains such as quantified information leakage, probabilistic reasoning, network reliability, neural network verification, and more. Owing to the #P-hardness of the problems, Stockmeyer initiated the study of the complexity of approximate counting. Stockmeyer showed that log n calls to an NP oracle are necessary and sufficient to achieve (ε,δ) guarantees. The hashing-based framework proposed by Stockmeyer has been very influential in designing practical counters over the past decade, wherein the SAT solver substitutes the NP oracle calls in practice. It is well known that an NP oracle does not fully capture the behavior of SAT solvers, as SAT solvers are also designed to provide satisfying assignments when a formula is satisfiable, without additional overhead. Accordingly, the notion of SAT oracle has been proposed to capture the behavior of SAT solver wherein given a Boolean formula, an SAT oracle returns a satisfying assignment if the formula is satisfiable or returns unsatisfiable otherwise. Since the practical state-of-the-art approximate counting techniques use SAT solvers, a natural question is whether an SAT oracle is more powerful than an NP oracle in the context of approximate model counting. The primary contribution of this work is to study the relative power of the NP oracle and SAT oracle in the context of approximate model counting. The previous techniques proposed in the context of an NP oracle are weak to provide strong bounds in the context of SAT oracle since, in contrast to an NP oracle that provides only one bit of information, a SAT oracle can provide n bits of information. We therefore develop a new methodology to achieve the main result: a SAT oracle is no more powerful than an NP oracle in the context of approximate model counting.
Cite as

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, and Kuldeep S. Meel. Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 123:1-123:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2023.123,
  author =	{Chakraborty, Diptarka and Chakraborty, Sourav and Kumar, Gunjan and Meel, Kuldeep S.},
  title =	{{Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle?}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{123:1--123:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.123},
  URN =		{urn:nbn:de:0030-drops-181750},
  doi =		{10.4230/LIPIcs.ICALP.2023.123},
  annote =	{Keywords: Model counting, Approximation, Satisfiability, NP oracle, SAT oracle}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.31
Clustering Permutations: New Techniques with Streaming Applications

Authors: Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the classical metric k-median clustering problem over a set of input rankings (i.e., permutations), which has myriad applications, from social-choice theory to web search and databases. A folklore algorithm provides a 2-approximate solution in polynomial time for all k = O(1), and works irrespective of the underlying distance measure, so long it is a metric; however, going below the 2-factor is a notorious challenge. We consider the Ulam distance, a variant of the well-known edit-distance metric, where strings are restricted to be permutations. For this metric, Chakraborty, Das, and Krauthgamer [SODA, 2021] provided a (2-δ)-approximation algorithm for k = 1, where δ≈ 2^{-40}. Our primary contribution is a new algorithmic framework for clustering a set of permutations. Our first result is a 1.999-approximation algorithm for the metric k-median problem under the Ulam metric, that runs in time (k log (nd))^{O(k)} nd³ for an input consisting of n permutations over [d]. In fact, our framework is powerful enough to extend this result to the streaming model (where the n input permutations arrive one by one) using only polylogarithmic (in n) space. Additionally, we show that similar results can be obtained even in the presence of outliers, which is presumably a more difficult problem.
Cite as

Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Clustering Permutations: New Techniques with Streaming Applications. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 31:1-31:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.31,
  author =	{Chakraborty, Diptarka and Das, Debarati and Krauthgamer, Robert},
  title =	{{Clustering Permutations: New Techniques with Streaming Applications}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{31:1--31:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.31},
  URN =		{urn:nbn:de:0030-drops-175340},
  doi =		{10.4230/LIPIcs.ITCS.2023.31},
  annote =	{Keywords: Clustering, Approximation Algorithms, Ulam Distance, Rank Aggregation, Streaming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.35
Pairwise Reachability Oracles and Preservers Under Failures

Authors: Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let G = (V, E) be a directed graph on n-nodes, and P ⊆ V× V be a set of vertex pairs in G. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we provide extremal bounds for sparse fault-tolerant reachability preservers, resilient to two or more failures. Prior to this work, such oracles and reachability preservers were widely studied for the special scenario of single-source and all-pairs settings. However, for the scenario of arbitrary pairs, no prior (non-trivial) results were known for dual (or more) failures, except those implied from the single-source setting. One of the main questions is whether it is possible to beat the O(n |P|) size bound (derived from the single-source setting) for reachability oracle and preserver for dual failures (or O(2^k n|P|) bound for k failures). We answer this question affirmatively. Below we summarize our contributions. - For an n-vertex directed graph G = (V, E) and P ⊆ V× V, we present a construction of O(n √{|P|}) sized dual fault-tolerant pairwise reachability oracle with constant query time. We further provide a matching (up to the word size) lower bound of Ω(n √{|P|}) on the size (in bits) of the oracle for the dual fault setting, thereby proving that our oracle is (near-)optimal. - Next, we provide a construction of O(n + min{|P|√ n,~n√{|P|}}) sized oracle with O(1) query time, resilient to single node/edge failure. In particular, for |P| bounded by O(√n) this yields an oracle of just O(n) size. We complement the upper bound with a lower bound of Ω(n^{2/3}|P|^{1/2}) (in bits), refuting the possibility of a linear-sized oracle for P of size ω(n^{2/3}). - We also present a construction of O(n^{4/3} |P|^{1/3}) sized pairwise reachability preservers resilient to dual edge/vertex failures. Previously, such preservers were known to exist only under single failure and had O(n+min{|P|√n,~n√ {|P|}}) size [Chakraborty and Choudhary, ICALP'20]. We also show a lower bound of Ω(n √{|P|}) edges on the size of dual fault-tolerant reachability preservers, thereby providing a sharp gap between single and dual fault-tolerant reachability preservers for |P| = o(n). - Finally, we provide a generic pairwise reachability preserver construction that provides a o(2^k n |P|) sized subgraph resilient to k failures, for any k ≥ 1. Before this work, we only knew of an O(2^k n |P|) bound implied from the single-source setting [Baswana, Choudhary, and Roditty, STOC'16].
Cite as

Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary. Pairwise Reachability Oracles and Preservers Under Failures. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2022.35,
  author =	{Chakraborty, Diptarka and Chatterjee, Kushagra and Choudhary, Keerti},
  title =	{{Pairwise Reachability Oracles and Preservers Under Failures}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.35},
  URN =		{urn:nbn:de:0030-drops-163768},
  doi =		{10.4230/LIPIcs.ICALP.2022.35},
  annote =	{Keywords: Fault-tolerant, Reachability Oracle, Reachability Preservers, Graph sparsification, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.11
Approximate Trace Reconstruction via Median String (In Average-Case)

Authors: Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We consider an approximate version of the trace reconstruction problem, where the goal is to recover an unknown string s ∈ {0,1}ⁿ from m traces (each trace is generated independently by passing s through a probabilistic insertion-deletion channel with rate p). We present a deterministic near-linear time algorithm for the average-case model, where s is random, that uses only three traces. It runs in near-linear time Õ(n) and with high probability reports a string within edit distance Õ(p² n) from s, which significantly improves over the straightforward bound of O(pn). Technically, our algorithm computes a (1+ε)-approximate median of the three input traces. To prove its correctness, our probabilistic analysis shows that an approximate median is indeed close to the unknown s. To achieve a near-linear time bound, we have to bypass the well-known dynamic programming algorithm that computes an optimal median in time O(n³).
Cite as

Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximate Trace Reconstruction via Median String (In Average-Case). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.11,
  author =	{Chakraborty, Diptarka and Das, Debarati and Krauthgamer, Robert},
  title =	{{Approximate Trace Reconstruction via Median String (In Average-Case)}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.11},
  URN =		{urn:nbn:de:0030-drops-155228},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.11},
  annote =	{Keywords: Trace Reconstruction, Approximation Algorithms, Edit Distance, String Median}
}
  • Refine by Type
  • 23 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 8 2025
  • 5 2023
  • 1 2022
  • 2 2021
  • 2 2020
  • Show More...

  • Refine by Author
  • 15 Chakraborty, Diptarka
  • 6 Das, Debarati
  • 3 Krauthgamer, Robert
  • 2 Bhanja, Koustav
  • 2 Choudhary, Keerti
  • Show More...

  • Refine by Series/Journal
  • 23 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Approximation algorithms analysis
  • 3 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 2 Theory of computation → Data structures design and analysis
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 5 Approximation Algorithms
  • 3 Edit Distance
  • 2 Center Problem
  • 2 Fault-tolerant
  • 2 Graph sparsification
  • Show More...

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact