CS Department, UCLA
Time: 12 noon
Place: Faraday Room 67-124 Engr IV
Error correction codes (Shannon 1948) allow one to send a message to a distant party, such that even if the communication channel is noisy, the other party is able to decode the correct message with high probability, while keeping the communication blowup linear in the length of the original message. However, when two parties wish to perform some interactive computation, where each message might depend on previous communication, a simple Shannon code cannot guarantee the success of the computation and other coding schemes must be devised.
In the first part of this talk we will survey some of the main interactive-communication coding schemes of the past 20 years and discuss their features and shortcomings. In the second part we will focus on Tree Codes, a notion that plays a fundamental role in such coding schemes, yet has no known efficient construction. We will show that the notion of Tree Codes can be relaxed into a strong-enough notion, namely Potent Tree Codes, that can be efficiently constructed and can be used for many interactive-communication coding schemes.