Jonathan Mosheiff

In contrast, every previous construction using polynomial randomness required an exponentially larger list size. Our approach extends earlier work by Li and Wootters, (2021) on the list-decodability of random linear binary codes. We introduce alphabet-permutation (AP) codes, a new family of error-correcting codes defined by iteratively applying random coordinate-wise permutations to a fixed initial word. A special case recovers random additive codes and random binary linear codes, where each permutation corresponds to an additive shift over a finite field. We show that when these permutations are drawn from a suitably “mixing” distribution, the resulting code is almost surely list-recoverable with list size proportional to the inverse of the gap to capacity. Compared to any linear code, our construction achieves exponentially smaller list sizes at the same rate. Previously, only fully random codes were known to attain such parameters, requiring exponentially many random bits and offering no structure. In contrast, AP codes are structured and require only polynomially many random bits—providing the first such construction to match the list-recovery guarantees of random codes.