@comment{ generated by <http://infoscience.epfl.ch/> }

@InProceedings{ALGO-CONF-2007-002,
   abstract    = {We outline a procedure for using pseudorandom generators
                 to construct binary codes with good properties, assuming
                 the existence of sufficiently hard functions.
                 Specifically, we give a polynomial time algorithm, which
                 for every integers $n$ and $k$, constructs polynomially
                 many linear codes of block length $n$ and dimension $k$,
                 most of which achieving the Gilbert- Varshamov bound. The
                 success of the procedure relies on the assumption that
                 the exponential time class of $E := DTIME[2^{O(n)}]$ is
                 not contained in the sub-exponential space class
                 $DSPACE[2^{o(n)}]$. The methods used in this paper are by
                 now standard within computational complexity theory, and
                 the main contribution of this note is observing that they
                 are relevant to the construction of optimal codes. We
                 attempt to make this note self contained, and describe
                 the relevant results and proofs from the theory of
                 pseudorandomness in some detail.},
   address     = { },
   affiliation = {EPFL},
   author      = {Cheraghchi, Mahdi and Shokrollahi, Amin and Wigderson, Avi},
   booktitle   = {Allerton 2006},
   details     = {http://infoscience.epfl.ch/record/101078},
   documenturl = {http://infoscience.epfl.ch/record/101078/files/final.pdf},
   keywords    = {algoweb_misc},
   location    = {Allerton House, IL, USA},
   note        = {Invited paper},
   oai-id      = {oai:infoscience.epfl.ch:101078},
   oai-set     = {conf},
   publisher   = { },
   review      = {REVIEWED},
   series      = { },
   status      = {PUBLISHED},
   title       = {Computational {H}ardness and {E}xplicit {C}onstructions
                 of {E}rror {C}orrecting {C}odes},
   unit        = {ALGO},
   url         = {http://www.csl.uiuc.edu/allerton/},
   year        = 2006
}