Skip to content Skip to navigation
Computer Science Department Colloquium
7/1/2016 11:00 am
Core A (Room 301)

Between Shannon and Hamming: Codes against causal adversaries

Sidharth Jaggi, Chinese University of Hong Kong

Faculty Host: Swastik Kopparty

Abstract

An adversary wishes to corrupt stored (or transmitted) data, but operates in an information-limited manner. Some examples of such limitations are when the adversary can only see some noisy version of Alice's transmission, or can only view those transmissions causally. We determine the capacity of some classes of such channels, and computationally efficient schemes achieving these capacities in some models (in particular over large alphabets). This is an overview of a long line of classical results, and also work done over the last few years (with an emphasis on a flurry of recent results) in collaboration Bikash Kumar Dey, Anand Dilip Sarwate, Michael Langberg, Zitan Chen, Mayank Bakshi, Qiaosheng Zhang (Eric), Alex Sprintson, and Swanand Kadhe.