Yaakobi, Eitan and Schwartz, Moshe and Langberg, Michael and Bruck, Jehoshua
(2013)
Sequence Reconstruction for Grassmann Graphs and Permutations.
California Institute of Technology
, Pasadena, CA.
(Unpublished)
https://resolver.caltech.edu/CaltechAUTHORS:20130215-095250632
![[img]](https://authors.library.caltech.edu/36948/1.hassmallThumbnailVersion/etr123.pdf)  Preview |
|
PDF
See Usage Policy.
202Kb |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130215-095250632
Abstract
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 t-metric for some special cases of
d and r.
Item Type: | Report or Paper (Technical Report) |
---|
Related URLs: | |
---|
ORCID: | |
---|
Additional Information: | This work was supported in part by an NSF grant ECCS-0801795 and a
BSF grant 2010075. |
---|
Group: | Parallel and Distributed Systems Group |
---|
Funders: | Funding Agency | Grant Number |
---|
NSF | ECCS-0801795 | Binational Science Foundation (BSF) | 2010075 |
|
---|
Other Numbering System: | Other Numbering System Name | Other Numbering System ID |
---|
Paradise | ETR123 |
|
---|
Record Number: | CaltechAUTHORS:20130215-095250632 |
---|
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20130215-095250632 |
---|
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. |
---|
ID Code: | 36948 |
---|
Collection: | CaltechPARADISE |
---|
Deposited By: |
Kristin Buxton
|
---|
Deposited On: | 15 Feb 2013 19:29 |
---|
Last Modified: | 22 Nov 2019 09:58 |
---|
Repository Staff Only: item control page