An official website of the United States government
Lee, James R.
(Ed.)
This content will become publicly available on December 15, 2026
Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
More Like this
-
-
This paper proposes a nested low-density parity-check (LDPC) code design. Combining this nested LDPC code with the random access coding strategy introduced by Yavas, Kostina, and Effros yields a random access LDPC (RA-LDPC) code for reliable communication in random access communication environments where neither the transmitters nor the receiver knows which or even how many transmitters wish to communicate at each moment. Coordination is achieved using sparse scheduled feedback. Bounds on the finite-blocklength performance of the RA-LDPC code under maximum likelihood (ML) decoding are derived using both error exponent and dispersion style analyses. Results include bounds on the penalty of the RA-LDPC code as a function of the LDPC code densities.more » « less
-
Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, by applying certain operations to an explicit mother code. Among them, one of the most well studied operations is random puncturing, where a series of works culminated in the work of Guruswami and Mosheiff (FOCS’ 22), which showed that a random puncturing of a low-biased code is likely to possess almost all interesting local properties of RLCs. In this work, we provide an in-depth study of another, dual operation of random puncturing, known as random shortening, which can be viewed equivalently as random puncturing on the dual code. Our main results show that for any small , by starting from a mother code with certain weaker conditions (e.g., having a large distance) and performing a random (or even pseudorandom) shortening, the new code is -biased with high probability. Our results hold for any field size and yield a shortened code with constant rate. This can be viewed as a complement to random puncturing, and together, we can obtain codes with properties like RLCs from weaker initial conditions. Our proofs involve several non-trivial methods of estimating the weight distribution of codewords, which may be of independent interest.more » « less
-
A bstract In holographic CFTs satisfying eigenstate thermalization, there is a regime where the operator product expansion can be approximated by a random tensor network. The geometry of the tensor network corresponds to a spatial slice in the holographic dual, with the tensors discretizing the radial direction. In spherically symmetric states in any dimension and more general states in 2d CFT, this leads to a holographic error-correcting code, defined in terms of OPE data, that can be systematically corrected beyond the random tensor approximation. The code is shown to be isometric for light operators outside the horizon, and non-isometric inside, as expected from general arguments about bulk reconstruction. The transition at the horizon occurs due to a subtle breakdown of the Virasoro identity block approximation in states with a complex interior.more » « less
