000101078 001__ 101078
000101078 005__ 20190316233938.0
000101078 037__ $$aCONF
000101078 245__ $$aComputational Hardness and Explicit Constructions of Error Correcting Codes
000101078 269__ $$a2006
000101078 260__ $$c2006
000101078 336__ $$aConference Papers
000101078 500__ $$aInvited paper
000101078 520__ $$aWe 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.
000101078 6531_ $$aalgoweb_coding
000101078 6531_ $$aalgoweb_tcs
000101078 700__ $$aCheraghchi, Mahdi
000101078 700__ $$0241952$$aShokrollahi, Amin$$g156849
000101078 700__ $$aWigderson, Avi
000101078 7112_ $$a44th Allerton Conference on Communication, Control and Computing$$cAllerton House, IL, USA$$dSeptember 27-September 29, 2006
000101078 773__ $$tAllerton 2006
000101078 8564_ $$uhttp://www.csl.uiuc.edu/allerton/$$zURL
000101078 8564_ $$s124971$$uhttps://infoscience.epfl.ch/record/101078/files/final.pdf$$yn/a$$zn/a
000101078 909C0 $$0252198$$pALGO$$xU10735
000101078 909CO $$ooai:infoscience.tind.io:101078$$pconf$$pIC$$qGLOBAL_SET
000101078 917Z8 $$x276415
000101078 917Z8 $$x156849
000101078 937__ $$aALGO-CONF-2007-002
000101078 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000101078 980__ $$aCONF