Clone of Reliable communication over noisy channels by Guessing Random Additive Noise Decoding - Joint Heriot Watt AMS and University of Edinburgh Numerical Analysis seminar Part 2

In 1948 Claude Shannon published his remarkable paper "A Mathematical Theory of Communication", which formed the basis for the digital communication revolution that was to follow, and gave rise to the field of Information Theory. As part of that ground-breaking work, he identified the greatest rate at which data can be communicated over a noisy channel, and also provided an algorithm for achieving it. Despite its mathematical elegance, his algorithm is impractical, and much work in the intervening 70 years has focused on identifying more practical approaches that enable reliable communication at high rates. That work is ongoing and, for example, Polar Codes, first introduced by Erdal Arikan in 2009, have recently been adopted as one of the two coding schemes to be used in the 5G cellular standard.
In this two part talk we revisit communication over a noisy channel through the lens of a new universal channel decoding algorithm called GRAND (Guessing Random Additive Noise Decoding), which we introduced in 2018. GRAND has surprising practical and theoretical features that set it apart from earlier approaches. The first part of this talk provides an introduction to the problem of reliable communication and focuses on an algorithmic description of GRAND, attempting to explain why we are investing significant effort in its development. The second part of the talk contains gory detail of the mathematics that underpins the algorithm's theoretical analysis, a probabilistic topic called Guesswork whose formalism dates back to 1994. Analysis of GRAND provides an alternate means for proving of Shannon's original channel coding theorem, giving rise to several new insights along the way. In both parts of the presentation, ongoing work and open problems will be discussed.
The talk is based on collaborative work with Muriel Medard and her group at MIT.