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.