Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 08/19: Shashwat Silas (Google)

David Wajc wajc at
Thu Aug 19 09:05:51 PDT 2021

Gentle reminder: theory lunch starting in three hours, with talk starting
half an hour after that. See you there!


On Mon, 16 Aug 2021 at 11:40, David Wajc <wajc at> wrote:

> Hi all,
> This week's theory lunch will take place Thursday at noon (PDT), at this
> zoom room
> <>. As
> usual, we'll start with some socializing, followed by a talk starting at
> 12:30pm.
> 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.
> Cheers,
> David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list