The sequence reconstruction problem for permutations with the Hamming distance Full article
| Journal |
Cryptography and Communications
ISSN: 1936-2447 , E-ISSN: 1936-2455 |
||||||||
|---|---|---|---|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 16, Pages: 1033–1057 Pages count : DOI: 10.1007/s12095-024-00717-y | ||||||||
| Tags | Sequence reconstruction · Permutation codes · Hamming distance · Cayley graph | ||||||||
| Authors |
|
||||||||
| Affiliations |
|
Funding (1)
| 1 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
Abstract:
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 = 2r. Moreover, we give a lower bound on the largest intersection of two metric balls for d = 2r − 1.
Cite:
Wang X.
, Konstantinova E.V.
The sequence reconstruction problem for permutations with the Hamming distance
Cryptography and Communications. 2024. V.16. P.1033–1057. DOI: 10.1007/s12095-024-00717-y WOS Scopus РИНЦ OpenAlex
The sequence reconstruction problem for permutations with the Hamming distance
Cryptography and Communications. 2024. V.16. P.1033–1057. DOI: 10.1007/s12095-024-00717-y WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Aug 5, 2023 |
| Accepted: | Apr 18, 2024 |
| Published online: | May 2, 2024 |
| Published print: | Sep 11, 2024 |
Identifiers:
| Web of science: | WOS:001215062500001 |
| Scopus: | 2-s2.0-85191941378 |
| Elibrary: | 67380843 |
| OpenAlex: | W4396586747 |