TY - GEN
T1 - Sequence reconstruction for Grassmann graphs and permutations
AU - Yaakobi, Eitan
AU - Schwartz, Moshe
AU - Langberg, Michael
AU - Bruck, Jehoshua
PY - 2013
Y1 - 2013
N2 - The sequence-reconstruction problem was first proposed by Levenshtein in 2001. This problem studies the model where the same word is transmitted over multiple channels. If the transmitted word belongs to some code of minimum distance d and there are at most r errors in every channel, then the minimum number of channels that guarantees a successful decoder (under the assumption that all channel outputs are distinct) has to be greater than the largest intersection of two balls of radius r and with distance at least d between their centers. This paper studies the combinatorial problem of computing the largest intersection of two balls for two cases. In the first part we solve this problem in the Grassmann graph for all values of d and r. In the second part we derive similar results for permutations under Kendall's τ-metric for some special cases of d and r.
AB - The sequence-reconstruction problem was first proposed by Levenshtein in 2001. This problem studies the model where the same word is transmitted over multiple channels. If the transmitted word belongs to some code of minimum distance d and there are at most r errors in every channel, then the minimum number of channels that guarantees a successful decoder (under the assumption that all channel outputs are distinct) has to be greater than the largest intersection of two balls of radius r and with distance at least d between their centers. This paper studies the combinatorial problem of computing the largest intersection of two balls for two cases. In the first part we solve this problem in the Grassmann graph for all values of d and r. In the second part we derive similar results for permutations under Kendall's τ-metric for some special cases of d and r.
UR - https://www.scopus.com/pages/publications/84890319209
U2 - 10.1109/ISIT.2013.6620351
DO - 10.1109/ISIT.2013.6620351
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84890319209
SN - 9781479904464
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 874
EP - 878
BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013
Y2 - 7 July 2013 through 12 July 2013
ER -