Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib, C. S. Karthik · 2024
The Ulam distance of two permutations on$[n]$is$n$minus the length of their longest common subsequence. In this paper, we show that for every$\varepsilon > 0$, there exists some$\alpha > 0$, and an infinite set$\Gamma\subseteq \mathbb{N}$, such that for all$n\in \Gamma$, there is an explicit set$C_{n}$of$(n!)^{\alpha}$many permutations on$[n]$, such that every pair of permutations in$C_{n}$has pairwise Ulam distance at least$(1-\epsilon)\cdot n$. Moreover, we can compute the$i^{\text{th}}$permutation in$C_{n}$in poly$(n)$time and can also decode in poly$(n)$time, a permutation$\pi$on$[n]$to its closest permutation$\pi^{*}$in$C_{n}$, if the Ulam distance of$\pi$and$\pi^{*}$is less than$\frac{(1-\varepsilon)n}{4}$. Previously, it was implicitly known by combining works of Goldreich and Wigderson [Israel Journal of Mathematics'23] and Farnoud, Skachek, and Milenkovic [IEEE Transactions on Information Theory'13] in a black-box manner, that it is possible to explicitly construct$(n!)^{\Omega(1)}$many permutations on$[n]$, such that every pair of them have pairwise Ulam distance at least$\frac{n}{6}\cdot(1-\varepsilon)$, for any$\varepsilon > 0$, and the bound on the distance can be improved to$\frac{n}{4}\cdot(1-\varepsilon)$if the construction of Goldreich and Wigderson is directly analyzed in the Ulam metric.