On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes

We determine, up to an additive constant 2, the minimum depth required to encode asymptotically good error-correcting codes using a linear number of wires. The inverse-Ackermann-type upper bound is guided by an encoding circuit construction due to Gál et al. [IEEE Trans. Inform. Theory 59(10), pp. 6611-6627, 2013] (which the authors showed asymptotically optimal for constant depths), but applies some new ideas in the construction and analysis to obtain shallower linear-size circuits. We also show our codes can obtain any constant rate and constant relative distance within the Gilbert-Varshamov bounds. The lower bound, which we credit to Gál et al., since it directly follows their method (although not explicitly claimed or fully verified in that work), is obtained by making some constants explicit in a graph-theoretic lemma of Pudlák, extending it to super-constant depths. We also study a subclass of MDS codes \(C: \mathbb {F}^n \rightarrow \mathbb {F}^m\) characterized by the Hamming-distance relation \({{\,\textrm{dist}\,}}(C(x), C(y)) \ge m - {{\,\textrm{dist}\,}}(x, y) + 1\) for any distinct \(x, y \in \mathbb {F}^n\) . (For linear codes this is equivalent to the generator matrix being totally invertible.) We call these superconcentrator-induced codes, and we show their tight connection with superconcentrators. Specifically, we observe that any linear or nonlinear circuit encoding a superconcentrator-induced code must be a superconcentrator graph, and any superconcentrator graph can be converted to a linear circuit, over a sufficiently large field (exponential in the size of the graph), encoding a superconcentrator-induced code.