Speaker: The Nguyen (UIUC)
Title: Permutation codes in Levenshtein, Ulam and Generalized Kendall--tau Metrics
Abstract: Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall--tau metrics. In this work, we first show a logarithmic improvement on the Gilbert--Varshamov lower bound of the maximum size of a permutation code capable of correcting $t$ deletions. Then, we present a new connection between different kinds of distances over two permutations, including Hamming, Levenshtein, Ulam, and generalized Kendall--tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permutation codes in Levenshtein, Ulam, and generalized Kendall--tau metrics with better size. In particular, we show that there exist permutation codes of length $n$ for correcting $t$ deletions with at most $(3t+1) \log n+o(\log n)$ bits of redundancy. If time permits, we present the construction of our permutation codes for correcting $t$ deletions with a specific decoding process. This is joint work with Yeow Meng Chee, Van Khu Vu, and Shuche Wang.
