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

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels
event speaker icon
Jad Silbak (Haifa University)
event date icon
Wednesday, 26.10.2016, 12:30
event location icon
Taub 201
Guruswami and Smith (Journal of the ACM, to appear) present a construction for an explicit codes for additive channels (channels that can induce a fixed error) that succeeds with high probability.

Furthermore Guruswami and Smith gave an explicit construction against channels of size n^c if we provide the encoding and decoding with public shared randomness (Monte-Carlo construction).

In this paper we solve several open problems posed by Guruswami and Smith:
1. We show a fully explicit construction for bonded channels under standard hardness assumptions.
2. We present a fully explicit unconditional construction for logarithmic space online channels.
3. We consider a tighter notion of explicitness in which the run time of the encoding and decoding is a fixed polynomial (does not depend on the complexity of the channel), and give a fully explicit construction for superpolynomial size circuits of constant depth.

This is a joint work with Ronen Shaltiel.