Abstract
A stochastic code is a pair of encoding and decoding procedures where Encoding procedure receives a k bit message m, and a d bit uniform string S. The code is (p,L)listdecodable against a class C of "channel functions" from n bits to n bits, if for every message m and every channel C in C that induces at most $pn$ errors, applying decoding on the "received word" C(Enc(m,S)) produces a list of at most L messages that contain m with high probability (over the choice of uniform S). Note that both the channel C and the decoding algorithm Dec do not receive the random variable S. The rate of a code is the ratio between the message length and the encoding length, and a code is explicit if Enc, Dec run in time poly(n).
Guruswami and Smith (J. ACM, to appear), showed that for every constants 0 < p < 1/2 and c>1 there are MonteCarlo explicit constructions of stochastic codes with rate R >= 1H(p)epsilon that are (p,L=poly(1/epsilon))list decodable for size n^c channels. MonteCarlo, means that the encoding and decoding need to share a public uniformly chosen poly(n^c) bit string Y, and the constructed stochastic code is (p,L)list decodable with high probability over the choice of Y.
Guruswami and Smith pose an open problem to give fully explicit (that is not MonteCarlo) explicit codes with the same parameters, under hardness assumptions. In this paper we resolve this open problem, using a minimal assumption: the existence of polytime computable pseudorandom generators for small circuits, which follows from standard complexity assumptions by Impagliazzo and Wigderson (STOC 97).
Guruswami and Smith also asked to give a fully explicit unconditional constructions with the same parameters against O(log n)space online channels. (These are channels that have space O(log n) and are allowed to read the input codeword in one pass). We resolve this open problem.
Finally, we consider a tighter notion of explicitness, in which the running time of encoding and listdecoding algorithms does not increase, when increasing the complexity of the channel. We give explicit constructions (with rate approaching 1H(p) for every p <= p_0 for some p_0>0) for channels that are circuits of size 2^{n^{Omega(1/d)}} and depth d. Here, the running time of encoding and decoding is a fixed polynomial (that does not depend on d).
Our approach builds on the machinery developed by Guruswami and Smith, replacing some probabilistic arguments with explicit constructions. We also present a simplified and general approach that makes the reductions in the proof more efficient, so that we can handle weak classes of channels.
BibTeX  Entry
@InProceedings{shaltiel_et_al:LIPIcs:2016:6668,
author = {Ronen Shaltiel and Jad Silbak},
title = {{Explicit ListDecodable Codes with Optimal Rate for Computationally Bounded Channels}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
pages = {45:145:38},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770187},
ISSN = {18688969},
year = {2016},
volume = {60},
editor = {Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6668},
URN = {urn:nbn:de:0030drops66682},
doi = {10.4230/LIPIcs.APPROXRANDOM.2016.45},
annote = {Keywords: Error Correcting Codes, List Decoding, Pseudorandomness}
}
Keywords: 

Error Correcting Codes, List Decoding, Pseudorandomness 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) 
Issue Date: 

2016 
Date of publication: 

06.09.2016 