Codes for Adversaries: Between Worst-Case and Average-Case Jamming
By Bikash Kumar Dey, IIT Bombay, India, bikash@ee.iitb.ac.in | Sidharth Jaggi, University of Bristol, UK, sid.jaggi@bristol.ac.uk | Michael Langberg, University at Buffalo, USA, mikel@buffalo.edu | Anand D. Sarwate, Rutgers University, USA, anand.sarwate@rutgers.edu | Yihan Zhang, IST Austria, Austria, zephyr.z798@gmail.com
Abstract
Over the last 70 years, information theory and coding has 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 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/worstcase view may be too pessimistic. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes.
Codes for Adversaries: Between Worst-Case and Average-Case Jamming
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 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. This monograph takes up the challenge of studying adversarial channel models that lie between the Shannon and Hamming extremes.
