Research output: Contribution to journal › Article › peer-review
The sequence reconstruction problem for permutations with the Hamming distance. / Wang, Xiang; Konstantinova, Elena V.
In: Cryptography and Communications, Vol. 16, No. 5, 09.2024, p. 1033-1057.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - The sequence reconstruction problem for permutations with the Hamming distance
AU - Wang, Xiang
AU - Konstantinova, Elena V.
N1 - The authors are very grateful to both referees for carefully reviewing the manuscript and for making many useful suggestions which greatly improved the paper. Our special thanks go to the anonymous referee who suggests to give more explanations in a few proofs. The work of Xiang Wang is supported by the National Natural Science Foundation of China (Grant No. 12001134), and the work of Elena V. Konstantinova is supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-281 with the Ministry of Science and High Education of the Russian Federation.
PY - 2024/9
Y1 - 2024/9
N2 - 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.
AB - 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.
KW - 05C25
KW - 68P30
KW - 94A15
KW - Cayley graph
KW - Hamming distance
KW - Permutation codes
KW - Sequence reconstruction
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85191941378&origin=inward&txGid=4bd6314696fe2ced3a805923203b52d2
UR - https://www.mendeley.com/catalogue/68e0abbd-d7e8-3a31-bd3b-40d653f4d95c/
U2 - 10.1007/s12095-024-00717-y
DO - 10.1007/s12095-024-00717-y
M3 - Article
VL - 16
SP - 1033
EP - 1057
JO - Cryptography and Communications
JF - Cryptography and Communications
SN - 1936-2447
IS - 5
ER -
ID: 61115900