Codes for Adversaries - Between Worst-Case and Average-Case Jamming

Michael Langberg (SUNY Buffalo)

Over the last 70 years, information theory and coding have enabled communication technologies that have had an astounding impact on our lives. This is possible due to the match between encoding/decoding strategies and corresponding channel models. Traditional studies of channels have mostly taken one of two extremes: Shannon-theoretic models are inherently average-case in which channel noise is governed by a memoryless stochastic process whereas coding-theoretic (referred to as “Hamming”) models take a worst-case, adversarial, view of the noise. However, for several existing and emerging communication systems, the Shannon/average-case view may be too optimistic, whereas the Hamming/worst-case view may be too pessimistic. In this talk, I will survey a collection of results on the study of channel models that fall between the Shannon and Hamming perspectives.

The talk is based on joint works with Z. Chen, A. Budkuley, B. K. Dey, I. Haviv, S. Jaggi, A. D. Sarwate, C. Wang, and Y. Zhang.

Recorded Talk