|
The Information Theory and Applications Center is dedicated to the study of information theory fundamentals and their relations to communications, computer- and life-sciences, finance, statistics, and related disciplines. The center supports both original research and educational activities in these areas. 
Wednesday, 11.11.09, 2:00 PM - 3:00 PM, 4004 Atkinson Hall, Seminar
Coding for online adversaries Michael Langberg, The Open University of Israel In this talk we consider the communication of information in the presence of an "online" or "causal" adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x=(x_1,...,x_n) symbol-by-symbol over a communication channel. The (malicious) adversarial jammer can view the transmitted symbols x_i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online (or causal) manner. Namely, for each symbol x_i the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on x_j for j <= i. This is in contrast to the ``classical' adversarial jammer which may base its decisions on its complete knowledge of the codeword x. Friday, 11.13.09, 3:00 PM - 4:00 PM, EBU2, Room 479, Seminar Understanding Implicit Communication in Distributed Control Pulkit Grover, UC Berkeley In distributed systems, control actions often serve a dual purpose -- minimizing the immediate control cost, and communicating relevant information to help other controllers. Unfortunately, though this “implicit communication” is ubiquitous, it also seems to make such problems hard. General communication problems have been addressed quite successfully using information theory. In this talk we will see how information theory can help improve our understanding of implicit communication, and thereby, of distributed control. First, we focus on Witsenhausen's counterexample -- a deceptively simple distributed control problem that has remained unsolved for more than 40 years. It has been observed that an implicit channel connects the two controllers in the counterexample. Using information-theoretic techniques, we provide upper and lower bounds to the optimal cost, characterizing the optimal cost of Witsenhausen's counterexample (and its vector extensions) to within a constant factor uniformly over all problem parameters. The information-theoretic technique of dirty-paper coding provides the best upper bounds. Lower bounds are derived using concepts from lossy communication of a source and a large-deviations (or sphere-packing) technique. Next, we show that the implicit channel based understanding extends to other two-controller problems, providing solutions to within a constant factor for these problems. Information theory thus emerges as an important toolset for obtaining provably good solutions to distributed control problems. Joint work with Anant Sahai, Se Yong Park. | |
|
