Abstract: In the standard noisy communication model, Alice encodes a message using an error-correcting code and sends it to Bob, who decodes it after receiving the entire message and storing it in memory. In this talk, we'll explore what happens when Bob doesn't have enough memory to store the whole message and must instead decode it bit by bit as it arrives. We'll define what it means for a code to be stream-decodable and present nearly matching upper and lower bounds on the code length required in this setting.

This is based on joint works with Venkat Guruswami, Mihir Singhal, and Rachel Zhang.