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.
This talk will summarize works joint work Bikash Dey, Ishay Haviv, Sidharth Jaggi, and Anand Sarwate.
Michael Langberg is faculty member in the Computer Science department at the Open University of Israel. Previously, between 2003 and 2006, he was a postdoctoral scholar in the Computer Science and Electrical Engineering departments at the California Institute of Technology. He received his B.Sc. in mathematics and computer science from Tel-Aviv University in 1996, and his M.Sc. and Ph.D. in computer science from the Weizmann Institute of Science in 1998 and 2003 respectively.
Dr. Langberg’s research is in the fields of Theoretical Computer Science and Information Theory. His work focuses on the design and analysis of algorithms for combinatorial problems, emphasizing on algorithmic and combinatorial aspects of Information Theory, and on probabilistic methods in combinatorics.
