License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.47
URN: urn:nbn:de:0030-drops-75964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7596/
Guruswami, Venkatesan ;
Li, Ray
Efficiently Decodable Codes for the Binary Deletion Channel
Abstract
In the random deletion channel, each bit is deleted independently with probability p. For the random deletion channel, the existence of codes of rate (1-p)/9, and thus bounded away from 0 for any p < 1, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate c_0 (1-p) for an absolute constant c_0 > 0.
BibTeX - Entry
@InProceedings{guruswami_et_al:LIPIcs:2017:7596,
author = {Venkatesan Guruswami and Ray Li},
title = {{Efficiently Decodable Codes for the Binary Deletion Channel}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {47:1--47:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7596},
URN = {urn:nbn:de:0030-drops-75964},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.47},
annote = {Keywords: Coding theory, Combinatorics, Synchronization errors, Channel capacity}
}
|
Keywords: |
|
Coding theory, Combinatorics, Synchronization errors, Channel capacity |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
