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

Link to this comparison view

en:group:semsem:all:20070215 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +---- dataentry seminar ----
 +date_dt : 2007.02.15
 +title : Computational Hardness and Explicit Constructions of Error Correcting Codes (Part I)
 +speaker : <a href="​http://​algo.epfl.ch/​index.php?​p=group_members_mahdi">​Mahdi Cheraghchi</​a>​
 +affiliation :  ALGO+LMA
 +time : 16h15-17h15
 +room : BC129
 +table : seminars
 +==== 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)}]$.