The Taub Faculty of Computer Science Events and Talks

Guruswami and Smith (J. ACM 2016) considered codes for channels that are computationally bounded and flip at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel (which flips each bit independently with probability p) but weaker than Hamming’s channels (which may flip at most a p-fraction of the bits, and are computationally unbounded). The goal of this area is to construct codes against channels that are computationally bounded (e.g., bounded memory channels, or channels that are poly-size circuits). In this talk I will explain this direction, focusing on a recent result by Shaltiel and Silbak (FOCS 2022) that consider channels that can be implemented by poly-size circuits. The main result of this work is a code that: - Achieves optimal rate of 1-H(p) (matching the capacity of binary symmetric channels, and beating the capacity of Hamming channels). - Has poly-time encoding and decoding algorithms, after a randomized joint pre-processing stage (this is often referred to as a "Monte-Carlo construction"). Our techniques rely on ideas from coding theory, pseudorandomness and cryptography. This is a joint work with Jad Silbak.