 |
|
< Back Wednesday, November 11, 2009 
Location: 4004 Atkinson Hall 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. In this talk, we study codes for online adversaries, and present several (some surprising) results. We study the case of communication over both binary and arbitrarily large alphabets. More generally, for a delay parameter d, we study the scenario in which the jammer's decision on the corruption of x_i must depend solely on x_j for j <= i - d. We extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. The latter corresponds, for example, to communication in the wireless setting. The talk is designed for a general EE/CS audience and will not assume any prior knowledge on the topic at hand. Joint work with Sidharth Jaggi and Bikash Dey. Presenter Bio Prof. Michael Langberg is a faculty member in the Computer Science Division at The Open University of Israel. Previously, he was a postdoc at Caltech. He completed my PhD studies at the Weizmann Institute of Science in 2003 under the supervision of Uri Feige. His studies and research are in the fields of Theoretical Computer Science and Information Theory. His broad area of interest is in the design and analysis of algorithms for combinatorial problems. He has special interest in algorithmic and combinatorial aspects of Information Theory and in the study of approximation algorithms for NP-hard problems. Closely related interests of include computational and combinatorial geometry, probabilistic methods in combinatorics, the use of randomization in computation, coding theory and computational complexity. |
