7 papers
Ulam Median is NP-hard for Four Permutations
Mursalin Habib
We show that computing a median under the Ulam distance is NP-hard even when the input consists of exactly four permutations. Previously, NP-hardness was known only for an unbounde…
Ulam Rank Aggregation Is Hard to Approximate for Four Rankings
Sk Ruhul Azgor, Diptarka Chakraborty, Le Van Cuong +3
We study the approximability of rank aggregation under the Ulam metric. In the \emph{Ulam median} problem, the goal is to find a ranking (permutation) minimizing the sum of its Ula…
An Optimal Algorithm for Binary Closest String
Nick Fischer, Mursalin Habib
We revisit the Binary Closest String problem, which asks, given a set of binary strings , to compute a string minimizing the maximum Hamming distance to …
Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
Vikrant Ashvinkumar, Mursalin Habib, Shashank Srivastava
Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. In this work, we give improved deterministic and randomized algorith…
Hardness of Median and Center in the Ulam Metric
Nick Fischer, Elazar Goldenberg, Mursalin Habib +1
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 fundamenta…
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4
A function is called an isometric embedding of the -dimensional Hamming metric space to the -dimensional edit metric space if, for all $x,y\in\{0,…
Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib, Karthik C. S
The Ulam distance of two permutations on is minus the length of their longest common subsequence. In this paper, we show that for every , there exists some…