000101078 001__ 101078
000101078 005__ 20180127203726.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_ $$iINTERNAL$$uhttps://infoscience.epfl.ch/record/101078/files/final.pdf$$xPUBLIC$$zn/a
000101078 909C0 $$0252198$$pALGO
000101078 909CO $$ooai:infoscience.tind.io:101078$$pIC$$pconf
000101078 917Z8 $$x276415
000101078 917Z8 $$x156849
000101078 937__ $$aALGO-CONF-2007-002
000101078 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000101078 980__ $$aCONF