A stochastic code is a pair of encoding and decoding procedures (Enc,Dec) where Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n, and a message m \in \{0,1\}^k is encoded by Enc(m,S) where S \from \{0,1\}^d is chosen uniformly by the encoder. The code is (p,L)-list-decodable against a class \mathcal{C} of ``channel functions'' C:\{0,1\}^n \to \{0,1\}^n if for every message m \in \{0,1\}^k,
and every channel C \in \mathcal{C} that induces at most pn errors, applying Dec on the ``received word'' C(Enc(m,S)), produces a list of at most L messages, that contains m with high probability (here the probability is over the choice of S \from \{0,1\}^d). Note that both the channel C, and the decoding algorithm Dec, \emph{do not} receive the random variable S. The rate of a code is R=k/n, and a code is explicit if Enc,Dec run in time \poly(n).

Guruswami and Smith (Journal of the ACM, to appear), showed that for every constants 0 1 there are \emph{Monte-Carlo} explicit constructions of stochastic codes with rate R \ge 1-H(p)-\epsilon that are (p,L=\poly(1/\epsilon))-list decodable for size n^c channels. Here, Monte-Carlo, 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 Monte-Carlo) explicit codes with the same parameters, under hardness assumptions. In this paper we resolve this open problem, using a minimal assumption: the existence of poly-time 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 also resolve this open problem.

Finally, we consider a tighter notion of explicitness, in which the running time of encoding and list-decoding algorithms does not increase, when increasing the complexity of the channel. We give explicit constructions (with rate approaching 1-H(p) for every p \le 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.

A stochastic code is a pair of encoding and decoding procedures (Enc,Dec) where Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n, and a message m \in \{0,1\}^k is encoded by Enc(m,S) where S \from \{0,1\}^d is chosen uniformly by the encoder. The code is (p,L)-list-decodable against a class \mathcal{C} of ``channel functions'' C:\{0,1\}^n \to \{0,1\}^n if for every message m \in \{0,1\}^k,
and every channel C \in \mathcal{C} that induces at most pn errors, applying Dec on the ``received word'' C(Enc(m,S)), produces a list of at most L messages, that contains m with high probability (here the probability is over the choice of S \from \{0,1\}^d). Note that both the channel C, and the decoding algorithm Dec, \emph{do not} receive the random variable S. The rate of a code is R=k/n, and a code is explicit if Enc,Dec run in time \poly(n).

Guruswami and Smith (Journal of the ACM, to appear), showed that for every constants 0 1 there are \emph{Monte-Carlo} explicit constructions of stochastic codes with rate R \ge 1-H(p)-\epsilon that are (p,L=\poly(1/\epsilon))-list decodable for size n^c channels. Here, Monte-Carlo, 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 Monte-Carlo) explicit codes with the same parameters, under hardness assumptions. In this paper we resolve this open problem, using a minimal assumption: the existence of poly-time 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 also resolve this open problem.

Finally, we consider a tighter notion of explicitness, in which the running time of encoding and list-decoding algorithms does not increase, when increasing the complexity of the channel. We give explicit constructions (with rate approaching 1-H(p) for every p \le 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.