Search Mailing List Archives
[theory-seminar] Theory Lunch 08/19: Shashwat Silas (Google)
David Wajc
wajc at stanford.edu
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!
Cheers,
David
On Mon, 16 Aug 2021 at 11:40, David Wajc <wajc at stanford.edu> wrote:
> Hi all,
>
> This week's theory lunch will take place Thursday at noon (PDT), at this
> zoom room
> <https://stanford.zoom.us/j/98932206471?pwd=YXdubytLVGNTbXhGeXFxNmJaVnhrUT09>. 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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210819/f3bdf1b4/attachment-0003.html>
More information about the theory-seminar
mailing list