Abstract
Typical time-efficient encoding and decoding algorithms for error correcting codes use linear space. We construct asymptotically good codes that can be deterministically encoded in almost linear time and sub-linear space, as well as asymptotically good codes that can be deterministically decoded in this complexity. The encodable codes are based on hashing. The decodable codes are based on locally correctable codes and a new efficient derandomization method.
The talk is based on joint work with Joshua Cook (University of Texas at Austin).