The sequence reconstruction problem for permutations with the Hamming distance | Sciact - Система учета научной деятельности ИМ СО РАН

The sequence reconstruction problem for permutations with the Hamming distance Научная публикация

Журнал

Cryptography and Communications
ISSN: 1936-2447 , E-ISSN: 1936-2455

Вых. Данные

Год: 2024, Том: 16, Страницы: 1033–1057 Страниц : 25 DOI: 10.1007/s12095-024-00717-y

Ключевые слова

Sequence reconstruction · Permutation codes · Hamming distance · Cayley graph

Авторы

Wang Xiang ¹ , Konstantinova Elena V. ^2,3,4

Организации

1	School of Mathematics, Statistics and Mechanics, Beijing University of Technology, 100124, Beijing, China
2	Sobolev Institute of Mathematics
3	Novosibirsk State University
4	Three Gorges Mathematical Research Center, China Three Gorges University, 8 University Avenue, 443002 Yichang, Hubei Province, China

Информация о финансировании (1)

Министерство науки и высшего образования РФ
Математический центр в Академгородке

075-15-2019-1613, 075-15-2022-281

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.

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

Поступила в редакцию:	5 авг. 2023 г.
Принята к публикации:	18 апр. 2024 г.
Опубликована online:	2 мая 2024 г.
Опубликована в печати:	11 сент. 2024 г.

Web of science:	WOS:001215062500001
Scopus:	2-s2.0-85191941378
РИНЦ:	67380843
OpenAlex:	W4396586747

БД	Цитирований
OpenAlex	1
Web of science	1
Scopus	1