Authors:  Anna Gál, University of Texas at Austin, Kristoffer Arnsfelt Hansen, Aarhus University, Michal Koucký, Institute of Mathematics of Czech Academy of Sciences and Aarhus University, Pavel Pudlák, Institute of Mathematics of Czech Academy of Sciences, Emanuele Viola, Northeastern University.

Error-correcting codes are fundamental in all digital data transmission systems. The idea behind error correcting codes is to encode a message with sufficient amount of redundancy in order to detect and correct errors in the transmitted message.Error correcting codes also form combinatorial objects of a fundamental nature with wide applications in many areas of computer science and mathematics.

This paper studies for the the complexity of encoding messages by (asymptotically good) error-correcting codes in constant time using massive parallelism. More precisely, we study the wire-complexity of unbounded-fanin constant depth circuits computing error-correcting codes in constant depth. For this measure of complexity we obtain precise bounds (up to a constant), all obtained for the first time.
To appear at: 44th ACM Symposium on Theory of Computing (STOC 2012). Paper available here.