Monday, April 25, 2016 - 12:00pm to 1:00pm
Location:Traffic 21 Classroom 6501 Gates & Hillman Centers
Speaker:AMEYA VELINGKER, Ph.D. Student http://www.cs.cmu.edu/~avelingk/
We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise. Recently, [Haeupler '14] showed that if an eps > 0 fraction of transmissions are corrupted adversarially or randomly, then it is possible to achieve a communication rate of 1-sqrt(eps)) and went on to conjecture that this rate is optimal for general input protocols. This stands in contrast to the classical setting of one-way communication in which error-correcting codes are known to achieve an optimal communication rate of 1-Theta(H(eps)) = 1 - Theta(eps*log(1/eps)). In this work, we show that the quadratically smaller rate loss of the one-way setting can also be achieved in interactive coding schemes for a very natural class of input protocols. We introduce the notion of average message length, or the average number of bits a party sends before receiving a reply, as a natural parameter for measuring the level of interactivity in a protocol. Moreover, we show that any protocol with average message length l = Omega(poly(1/eps)) can be simulated, with high probability, by a longer protocol with an optimal communication rate of 1-Theta(H(eps)) over an oblivious adversarial channel with error fraction eps. This shows that the capacity gap between one-way and interactive communication can be bridged even for very small (constant in eps) average message lengths, which is very likely to be found in many applications. Joint work with Bernhard Haeupler. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.