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

摘要

A stochastic code is a pair of encoding and decoding procedures ( Enc D ec ) where Enc : 0 1 k 0 1 d 0 1 n , and a message m 0 1 k is encoded by Enc ( m S ) where S rom 0 1 d is chosen uniformly by the encoder. The code is ( p L ) -list-decodable against a class of ``channel functions'' C : 0 1 n 0 1 n if for every message m 0 1 k , and every channel 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 rom 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 D ec run in time poly ( n ) .Guruswami and Smith (Journal of the ACM, to appear), showed that for every constants 01 there are emph{Monte-Carlo} explicit constructions of stochastic codes with rate R 1 ? H ( p ) ? that are ( p L = poly (1 )) -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 p 0 for some 0"> p 0 0 ) for channels that are circuits of size 2 n (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.