We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good ... more >>>

It has been known since [Zyablov and Pinsker 1982] that a random q-ary code of rate 1-H_q(\rho)-\eps (where 0<\rho<1-1/q, \eps>0 and H_q(\cdot) is the q-ary entropy function) with high probability is a (\rho,1/\eps)-list decodable code. (That is, every Hamming ball of radius at most \rho n has at most 1/\eps ... more >>>

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of O(1/\gamma)) and lower bound (of \Omega_p(\log (1/\gamma))) for the list-size needed to decode up to radius p with rate \gamma away from capacity, i.e., 1-h(p)-\gamma (here p\in (0,1/2) ... more >>>