The Taub Faculty of Computer Science Events and Talks

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.