EE Seminar: Dr. Ran Gelles (Princeton University)

~~(The talk will be given in English)

Dr. Ran Gelles
Department of Computer Science, Princeton University
Monday, January 26th, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

Interactive communication over channels with feedback and erasure channels: Capacity and Maximal noise resilience
Abstract
We consider coding protocols for interactive communication performed over two simple types of noisy channels: binary error channels with noiseless feedback and binary erasure channels. In both cases, the noise model is adversarial, where we assume at most \eps-fraction of the bits can be corrupted.
Our first result deals with the maximal rate obtainable by such coding schemes. Specifically, we give simple randomized, efficient protocols that achieve a rate of 1-O(H(\eps)) for both channel types. Such a rate is optimal for feedback channels and is conjectured to be optimal for erasure channels as well.
Next we consider the maximal noise that interactive protocols can withstand when communication is done over the above two channels (assuming some positive rate). For feedback channels, we show a tight upper and lower bounds: when the “order of speaking” is fixed (say, alternating), the bound on the noise is 1/6 in the binary case and 1/4 if parties are allowed to send symbols from a larger alphabet. When the “order of speaking” is not predetermined, the maximal noise becomes 1/3, regardless of the alphabet size of the channel.
For erasure channels with a large alphabet, we provide a protocol that matches the optimal tolerable erasure rate of 1/2 (Franklin et al., CRYPTO ’13) but operates in a much simpler and more efficient way. Translating this protocol to the case of a binary erasure channels yields a protocol that withstands at most 1/3 fraction of erasures.  Our protocols are simple, deterministic and computationally efficient.

Based on joint works (SODA’15,ITCS’15) with Klim Efremenko and Bernhard Haeupler