The Taub Faculty of Computer Science Events and Talks

In the talk I will survey a research direction which combines coding-theory and computational complexity. This direction was introduced by Lipton, and refined by Guruswami and Smith. The goal is to construct error correcting codes which correct errors that are introduced by computationally bounded channels. This is in contrast to Hamming’s standard model which assumes a bound on the fraction of bits that a channel may flip, but allows the channel to be computationally unbounded.

In recent work with Jad Silbak we give explicit constructions of codes with rate that beats the best possible rate of codes in Hamming’s standard model and matches the capacity of Shannon’s binary symmetric channels. These results are achieved against channels with small space, and channels that can be implemented by poly-size circuits (under a suitable hardness assumption).

My plan is to explain the model, survey the new results, and try to show some of the components that are used in these works.

Joint work with Jad Silbak.