Search Mailing List Archives
[theory-seminar] Theory Lunch 08/19: Shashwat Silas (Google)
wajc at stanford.edu
Mon Aug 16 11:40:20 PDT 2021
This week's theory lunch will take place Thursday at noon (PDT), at this
usual, we'll start with some socializing, followed by a talk starting at
Shashwat will tell us about: *Real-time decoding of rateless codes*
*Abstract:* Rateless codes have been widely studied in academia and are
used in several production software systems for networking. There are still
many interesting open problems to consider. We will have a brief
introduction to rateless codes and look at the problem of real-time
oblivious decoding of rateless codes.
Rateless codes are used for transmission of information across channels
whose rate of erasure is unknown. In such a code, an infinite stream of
encoding symbols can be generated from the message and sent across the
erasure channel, and the decoder can decode the message after it has
successfully collected a certain number of encoding symbols. A rateless
erasure code is real-time oblivious if rather than collecting encoding
symbols as they are received, the receiver either immediately decodes or
discards each symbol it receives.
Efficient real-time oblivious erasure correction uses a feedback channel in
order to maximize the probability that a received encoding symbol is
decoded rather than discarded. We construct codes which are real-time
oblivious, but require fewer feedback messages and have faster decoding
compared to previous work. Specifically, for a message of length *k*, we
improve the expected complexity of the feedback channel from O(k^(1/2)) to
O(1), and the expected decoding complexity from O(klog(k)) to O(k) Our
method involves using an appropriate block erasure code to first encode the
*k *message symbols, and then using a truncated version of the real-time
oblivious erasure correction of Beimel et al (2007) to transmit the encoded
message to the receiver, which then uses the decoding algorithm for the
outer code to recover the message.
Finally, we will look at simulations of non-oblivious models of real-time
decoding which have even better real-time decoding properties.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar