Speaker: Haim Permuter

Title: How to communicate via a binary erasure channel with feedback without repeated ones?

Abstract: In this talk we will present a simple and fundamental problem: communicating via a memoryless binary erasure channel with feedback without consecutive 1's. First, we will present the problem as a puzzle and provide a simple solution. We will prove its optimality using only counting, logic and basic probability arguments. Then we will show how we obtained the solution using information theory tools (such as the Directed information) and optimization tools (such as Dynamic Programming). In addition, we will present a new single-letter upper bound for unifilar channel with feedback that is tight for all known cases. The upper bound uses a new idea of having an auxiliary random graph rather than i.i.d. auxiliary variable that usually we use in multi-user problems. This talk is based on on joint work with Oron Sabag, Navin Kashyap and Henry Pfister .