Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision 		Previous revision
en:group:seminars:20070223 [2009/04/06 17:44]
127.0.0.1 external edit 		en:group:seminars:20070223 [2016/06/23 11:26] (current)
Line 1: Line 1:
- 
 ---- dataentry seminar ---- ---- dataentry seminar ----
-date_dt : 2007.02.23+date_dt : 2007-02-23
 title : Computational Hardness and Explicit Constructions of Error Correcting Codes (Part II) title : Computational Hardness and Explicit Constructions of Error Correcting Codes (Part II)
 speaker : Mahdi Cheraghchi speaker : Mahdi Cheraghchi
Line 11: Line 10:
 template:​datatemplates:​seminar template:​datatemplates:​seminar
 ----------------------- -----------------------
- 
- 
 ==== abstract ==== ==== 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)}]$. 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)}]$.