Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
event speaker icon
Ronen Shaltiel (Haifa University)
event date icon
Wednesday, 05.06.2024, 12:45
event location icon
Amado 719
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.