Coding Theory in Almost-Linear Time and Sub-Linear Space

Error correcting codes are invaluable both for communication and for computational complexity. In complexity they are the foundation of objects such as pseudorandom generators, probabilistically checkable proofs and delegation protocols.
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 condenser graphs. The decodable codes are based on locally correctable codes and a new efficient derandomization method. We believe that the new derandomization method is of independent interest.

The talk is based on joint works with Joshua Cook (University of Texas at Austin).