Theory Seminar: Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

ג'אד סילבאק (אונ' חיפה)
יום רביעי, 26.10.2016, 12:30
טאוב 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.

בחזרה לאינדקס האירועים