Between Shannon and Hamming: how bad can the channel be?: BLISS Seminar
Seminar | May 6 | 3-4 p.m. | 540 Cory Hall
Anand Sarwate, Rutgers
The information theory community has traditionally studied two different models for communication. The Shannon-theoretic model treats the channels impact as random, so codes must correct almost all error patterns of a given weight; this is an average-case analysis. The coding-theoretic (Hamming-theoretic?) model treats the channel as adversarial, so codes must correct all error patterns of a given weight; this is a worst-case analysis. Between the two lie several different models which can be modeled using a channel model (an AVC) in which the channel is controlled by an adversary. The difference between average- and worst-case is captured by explicitly modeling the information available to the adversary. I will describe some of these models and the key role played by coding strategies such as stochastic encoding and list decoding.
This talk may include joint work with Bikash Kumar Dey, Michael Gastpar, Sidharth Jaggi, Michael Langberg, and Carol Wang.