101078
20180317094151.0
CONF
Computational Hardness and Explicit Constructions of Error Correcting Codes
2006
2006
Conference Papers
Invited paper
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.
algoweb_coding
algoweb_tcs
Cheraghchi, Mahdi
Shokrollahi, Amin
156849
241952
Wigderson, Avi
44th Allerton Conference on Communication, Control and Computing
Allerton House, IL, USA
September 27-September 29, 2006
Allerton 2006
URL
http://www.csl.uiuc.edu/allerton/
n/a
124971
n/a
http://infoscience.epfl.ch/record/101078/files/final.pdf
oai:infoscience.tind.io:101078
IC
conf
ALGO
252198
U10735
276415
156849
ALGO-CONF-2007-002
EPFL
PUBLISHED
REVIEWED
CONF