---- dataentry seminar ---- date_dt : 2007-02-15 title : Computational Hardness and Explicit Constructions of Error Correcting Codes (Part I) speaker : Mahdi Cheraghchi affiliation : ALGO+LMA time : 16h15-17h15 room : BC129 table : seminars =================== template:datatemplates:seminar ----------------------- ==== 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)}]$.