Between Shannon and Hamming: how bad can the channel be?: BLISS Seminar

Seminar: EE: Berkeley Laboratory for Information and System Sciences (BLISS) | May 6 | 3-4 p.m. | 540 Cory Hall

 Anand Sarwate, Rutgers

 Electrical Engineering and Computer Sciences (EECS)

The information theory community has traditionally studied two different models for communication. The Shannon-theoretic model treats the channel’s 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.