Capacity-Achieving Codes with Inverse-Ackermann-Depth Encoders

Yuan Li

We prove that for any additive noise channel over ${\mathbb{F}}_q$, there exist error-correcting codes approaching channel capacity encodable by arithmetic circuits (with weighted ad…