REVIEW
Polynomial time decodable codes for the binary deletion channel
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Polynomial time decodable codes for the binary deletion channel
classification
cs.IT
cs.DSmath.IT
keywords
deletionchannelcodespolynomialrandomratetimeabsolute
read the original 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$.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.