The sequence reconstruction problem for permutations with the Hamming distance

• Published in: Cryptography and communications 2024, Vol.16 (5), p.1033-1057
• Main Authors: Wang, Xiang, Konstantinova, Elena V.
• Format: Article
• Language: English
• Subjects: Channels; Circuits; Coding and Information Theory; Communications Engineering; Computer Science; Data Structures and Information Theory; Information and Communication; Intersections; Lower bounds; Mathematics of Computing; Networks; Permutations; Reconstruction
• ISSN: 1936-2447; 1936-2455
• DOI: 10.1007/s12095-024-00717-y

V. Levenshtein first proposed the sequence reconstruction problem in 2001. This problem studies the same sequence from some set is transmitted over multiple channels, and the decoder receives the different outputs. Assume that the transmitted sequence is at distance d from some code and there are at most r errors in every channel. Then the sequence reconstruction problem is to find the minimum number of channels required to recover exactly the transmitted sequence that has to be greater than the maximum intersection between two metric balls of radius r , where the distance between their centers is at least d . In this paper, we study the sequence reconstruction problem of permutations under the Hamming distance. In this model we define a Cayley graph over the symmetric group, study its properties and find the exact value of the largest intersection of its two metric balls for d = 2 r . Moreover, we give a lower bound on the largest intersection of two metric balls for d = 2 r - 1 .