A puzzle: How to communicate via a binary erasure channel with feedback without repeated ones?
Friday, February 13, 2015 - 1:00pm to 2:00pm
Packard 202
Haim Permuter (BGU)
Abstract / Description: 

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, logics 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 Programing).

The talk will be given mostly on a whiteboard.

Based on Joint work with Oron Sabag from Ben-Gurion University and Navin Kashyap from Indian Institute of Science.


Haim Permuter received his B.Sc. (summa cum laude) from Ben-Gurion University (BGU) and Ph.D. from Stanford University, both in in Electrical Engineering, in 1997 and 2008, respectively. Between 1997-2004, he served as a scientific research officer in an R&D unit in the Israeli Defense Forces. In summer 2002 he worked for IBM, Almaden research center. He is a recipient of several rewards including Eshkol Fellowship, Wolf Award, Fulbright Fellowship, Stanford Graduate Fellowship, and Allon Fellowship. Haim joined the faculty of Electrical Engineering Department at BGU in Oct 2008, and is now an associate professor.