Papers for
data storage engineers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Explicit codes correct mixed insertions deletions and substitutions
Explicit Edit Codes via Multicoloring
Abstract: For any fixed integers $q\ge2$ and $t\ge1$, we construct explicit $q$-ary codes of length $n$ that correct any combination of at most $t$ insertions, deletions, and substitutions, with redundancy at most $2t\log_q n+O_{q,t}(\log\log n)$ $q$-ary symbols. This matches the leading redundancy term of Levenshtein's classical existential bound. Building on the standard graph-coloring approach, we use a prime-based multicoloring of the edit-confusion graph to assign multiple colors to each $q$-ary word of length $m<n$. Appending a short, edit-protected representation of an assigned color to the length-$m$ word yields a length-$n$ codeword. The choice among the assigned colors carries additional message information, thereby reducing the redundancy. The construction admits deterministic encoding and decoding in $\widetilde O_{q,t}(n^{6t+2})$ and $\widetilde O_{q,t}(n^{7t+2})$ time, respectively.
Explicit constructions reduce overlap in mathematical data sets
Explicit Subspace Evasive Sets via Subspace Designs
Abstract: Given a finite field $\mathbb F_q$, we say that a set $A\subseteq \mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\subseteq \mathbb F^n_q$ with bounded dimension $\dim(U)\leq r$, the intersection size $|A\cap U|$ is at most $c$. The probabilistic method shows the existence of $(r,c)$ subspace evasive sets with $|A| = q^{(1-ε) n}$ with $c = O(r/ε)$. However, the best explicit constructions by Dvir--Lovett (STOC 2012) and Ben-Aroya--Shinkar (CJTCS 2013) have $c$ growing as an exponential function of $r$. Here, we give an explicit construction of such subspace evasive set that achieves the intersection bound $c=O(\min(r\log(r/ε)/ε, r^2/ε))$ when both $r$ and $1/ε$ are constants. Our approach is simple and the key idea is to compose subspace design codes (Guruswami-Xing, STOC 2013) with a suitably chosen ``local'' subspace evasive set. As a corollary, we give the first construction of an explicit (strongly) capacity-achieving list-recoverable code with nearly optimal list size, circumventing all previously-known barriers to construction.
Constant query codes correct errors over real number grids
Constant query LCCs over the reals
Abstract: This note describes a new construction, found by ChatGPT Astra, of constant query Locally Correctable Codes (LCCs) over the real numbers. Prior constructions of constant query LCCs were exclusive to fields of positive characteristic and were conjectured not to exist over the reals. The construction uses low degree polynomial evaluations over an integer grid, together with a novel sampling procedure which outputs, for a given grid point $P$, a random quadratic curve through $P$ which intersects the grid in many other points (the decoding queries). The sampler is `smooth' in the sense that no grid point is queried with high probability. These codes have the additional property that the queried locations (the curve/grid intersections) are all nearby grid points.
Compression with privacy keeps data safe for sources with memory
Compression of Sources with Memory and Private Random Access
Abstract: Private local decoding imposes a stringent constraint on compression: the codeword bits used to recover a source symbol must reveal nothing about the remaining symbols beyond what the recovered symbol itself reveals. For memoryless sources, this constraint is known to be compatible with entropy-rate compression. We show that the same holds for any stationary ergodic source over a finite alphabet. Specifically, every rate above the entropy rate is achievable with exact privacy and error-free local decoding on a set of source sequences whose probability tends to one. In contrast, we exhibit non-ergodic sources for which private local decoding incurs a strictly positive rate penalty.
New bounds improve rates of hashing and trifferent codes
Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes
Abstract: We improve the probabilistic lower bounds on the rates of hash codes and list-recoverable codes. For perfect $q$-hashing, we prove $R_q>B_q$ for every $q\geq 3$. Our main result concerns non-perfect hashing. For every $q\geq 4$, we prove $R_{q,3}>B_{q,3}+\frac{1}{250000}.$ In particular, the case $q=9$, combined with the Tetra code, strictly improves the Körner-Marton lower bound $R_3\geq \frac14\log(9/5)$ for trifferent codes. We also extend the method to $(p,2,3)$-list recovery. For every $q\geq 4$ and $0\leq p<\frac{q-2}{12(q-1)}$, we prove $R_q^{\mathrm{LR}}(p)>B_q^{\mathrm{LR}}(p)$. For every fixed $0\leq p<1/18$, the rate improvement is bounded below by a positive constant independent of $q\geq 4$. The same holds for every fixed $0\le p<1/12$ when $q$ is sufficiently large.
Magnetic tape storage boosted by advanced reed solomon decoding method
Anchored Iterative Decoding of Reed-Solomon Product Codes for High-Rate Magnetic Tape Storage
Abstract: We present a decoding algorithm for a Reed--Solomon product code targeted at the demanding reliability requirements of modern magnetic tape storage. For a code $RS(256, 224)\times RS(175, 173)$ in a BSC we achieve post-decoding bit error rate (BER) of $10^{-20}$ at $\approx 5.3\times 10^{-3}$ raw BER while maintaining the common requirement to detect and correct 4 out of 32 dead tracks. We resolve two common problems of miscorrections and stall patterns that arise under such a high raw BER via simplified versions of anchor decoding and binary image analysis. The highest efficiency is achieved by performing an unlimited iterative decoder, which performs decoding iterations until no changes are made. We give an empirical analysis of the average number of iterations: below the raw BER of $5\times 10^{-3}$, four half-iterations are performed on average while improving substantially over a decoder that always performs 4 half-iterations. We provide a CPU implementation achieving 100-200 megabytes/s single-core throughput on a regular laptop and a design of a potential hybrid FPGA-CPU implementation of our decoder.
Random linear codes have sharp thresholds for local properties
A Universal Threshold Theory for Local Properties of Random Linear Codes
Abstract: Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\mathcal P$ is the code dimension at which the probability that an RLC in $\mathbb{F}_q^n$ satisfies $\mathcal P$ crosses $1/2$ in a sharp transition. We show that the threshold of a $b$-local property $\mathcal P$ is within $O(b)$ dimensions of the expectation threshold. This is the dimension predicted by the best union bound over covers of $\mathcal P$: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix is sampled from a small-bias distribution. Because our threshold characterization applies to all local properties, this derandomization also reaches properties beyond the scope of earlier reductions, including maximum loads in linear hashing for arbitrary input sets, rank-metric list decoding, and list decoding from insertion-deletion errors and burst errors. Our theorem unifies and strengthens prior works on row-symmetric and coordinate-wise linear characterizations, which located the threshold to within $O(q^{2b}\log_q n)$ and $O(b^2+nb/\log_2 q)$ dimensions, respectively. We obtain $O(b)$ error for every $b$-local property, independently of alphabet size. Under suitable pseudorandomness bounds, the rate loss vanishes for every $b=o(n)$, compared to $b=O(\log n)$ for earlier frameworks.
Lower bounds tighten limits on relaxed locally decodable codes
Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
Abstract: We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.
Binary codes correct multiple edits efficiently with low redundancy
Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
Abstract: We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.
Codes correct successive swaps with blockwise encoding and decoding
Concatenation Locality under Successive Adjacent Transpositions
Abstract: We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.
MDS codes built on hyperelliptic curves for better error correction
MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
Abstract: For every fixed genus $g\geq2$ and every $0<ρ<1$, we construct maximum distance separable (MDS) algebraic geometry codes over $\F_q$ for all sufficiently large odd squares $q$. Their parameters are $\bigl[n,\lfloorρn\rfloor,n-\lfloorρn\rfloor+1\bigr]_q$ with $n=\sqrt q+1+O_g(q^{1/4})$. The codes use full Riemann--Roch spaces on genus-$g$ hyperelliptic curves. They are not monomially equivalent to generalized Reed--Solomon (GRS) codes when $q$ is sufficiently large. An infinite subfamily has exact length $n=\sqrt q+2gq^{1/4}+1$.
Capacity limits for distributed linear computation depend on subspace cross-ratio
Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio
Abstract: $K$ users each observe a fixed linear function of common data over a finite field of characteristic $p$, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe $\boldsymbol{a}$, $\boldsymbol{b}$ and $\boldsymbol{a}+\boldsymbol{b}$ and the server wants $\boldsymbol{a}+λ\boldsymbol{b}$. The four functions span four lines in a plane with cross-ratio $λ$, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every $λ$, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, $λ=-1$, $λ=2$ or $2λ=1$, it is $2$: every zero-error code reveals $(\boldsymbol{a},\boldsymbol{b})$ to the server, so no code beats having two users send their observations. For $λ$ outside the prime subfield it is the cut-set bound $3/2$, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other $λ$ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for $λ$ outside the prime subfield. The four-line instance is also exact repair of one node of a $[4,2]$ MDS storage code, and the results translate to that setting.
TensorSSM improves tensor compression by memorizing spatial positions
TensorSSM: Memorizing Spatial Position in Dynamic State Space for Tensor Core Generation
Abstract: High-dimensional tensors are ubiquitous in real-world applications but lead to massive storage overhead. Functional tensor decomposition addresses this by employing neural networks to map element coordinates to tensor cores, significantly reducing the parameters for data compression. However, existing functional methods typically flatten high-order tensors into 1D sequences. This folding operation causes highly overlapping local coordinate sequences and struggles to capture complex cross-mode spatial dependencies, severely limiting their expressiveness on diverse datasets. To tackle these challenges, we propose TensorSSM, a novel Implicit Neural Representation (INR) for functional decomposition method that memorizes spatial positions within a dynamic State Space Model (SSM). Specifically, TensorSSM first decomposes mode-wise coordinates into sequences spit by K-ary rule, encoding spatial tokens from coarse to fine, which effectively captures spatial variations. Furthermore, we extend the SSM's state space to explicitly map cross-mode spatial dependencies, allowing inter-mode interactions to enhance the updates of each mode. By integrating cross-mode information from previous hidden states into the current state transitions, TensorSSM effectively expands tensor representation along two dimensions: the sequence dimension for coarse-to-fine spatial tokens, and the state dimension for cross-mode memorization. This design effectively integrates spatial information into the state space and the tensor core, substantially advancing the state adaptability and enhancing the expressiveness of the data compression. Extensive experiments demonstrate that TensorSSM achieves significantly high reconstruction accuracy and storage efficiency, exhibiting robust expressiveness across diverse tensor datasets without relying on strict spatial assumptions.
Improved code decoding methods reduce alphabet size significantly
Improved LCL Equivalences and Curve Decoding Alphabet Sizes
Abstract: Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-$R$ code $C \subset \mathbb{F}^n$ is $(\ell,δ,a,b)$-curve decodable if any degree-$\ell$ curve $u:\mathbb{F}\to\mathbb{F}^n$ that is $δ$-close to $C$ on at least $a$ points has at least $b\leq a$ nearby codewords lying on a degree-$\ell$ curve in $C$. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius $δ$ approaching $1-R$, but with large alphabets in $\ell$ and $η:=1-R-δ$. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of $(a,b)$. For $\ell=O(1)$, our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.
Polynomial time codes enable efficient symbol recovery from compressed data
Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
Abstract: Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.
Secure convertible codes protect data against partial eavesdropping
Constructions of Secure Convertible Codes
Abstract: Secure convertible codes, introduced by Zhang and Rashmi, achieve secrecy capacity under a passive eavesdropper model in which an eavesdropper is allowed to access any $\ell$ symbols from the initial and final codewords. In this paper, we construct two families of access-optimal secure convertible codes. The first family of codes based on Maximum Rank Distance (MRD) codes is constructed for all parameters in the merge and split regimes and requires a large field size. The second family of codes, constructed using Generalized Reed-Solomon codes, uses smaller fields but is applicable only for certain parameters in the merge and split regimes.
Deterministic methods improve Reed-Solomon error correction codes beyond limits
Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound
Abstract: We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).
Sum rank Reed Muller style codes unify and generalize known code families
Sum-rank analogues of Reed--Muller codes over Abelian Galois extensions
Abstract: Let $\mathbb L/\mathbb K$ be a finite Abelian Galois extension with a fixed decomposition $\mathrm{Gal}(\mathbb L/\mathbb K)=\langleσ_1\rangle\times\cdots\times\langleσ_m\rangle$. We show that the quotient of the multivariate skew polynomial ring $\mathbb L[x_1,\ldots,x_m;σ_1,\ldots,σ_m]$ by suitable central polynomials $H_1(x_1),\ldots,H_m(x_m)$ is isomorphic to a product of $t$ copies of $\mathrm{End}_{\mathbb K}(\mathbb L)$, so that one skew polynomial represents all blocks of a sum-rank metric space. The sum-rank weight of an element equals the rank of an associated Dickson matrix and of a generalized Moore matrix. Using this, we define sum-rank Reed--Muller-type codes and show that their dimension and minimum distance are given by the formulas for affine Cartesian codes with side lengths $\mathrm{deg}\,H_1,\ldots,\mathrm{deg}\,H_m$; the same holds for codes supported on lower sets. The family contains as special cases linearized Reed--Solomon codes, Gabidulin codes, rank-metric Reed--Muller codes, and affine Cartesian codes. Over finite fields, every linearized Reed--Muller code of Berardini and Caruso is, after a monomial change of variables, a monomial code in our framework. This gives the dimension of all these codes, and their exact minimum distance in every degree whenever the support is a lower set.
MDS codes extended to longer lengths with efficient new algorithm
Extension of MDS Codes over Finite Fields
Abstract: In this paper, we investigate extending of $[n,k,n-k+1]$ non-Reed--Solomon(non-RS) MDS codes to $[n+1,k,n-k+2]$ non-RS MDS codes. We develop a practical iterative algorithm for constructing longer MDS codes while preserving their non-RS structure. The proposed algorithm is inspired by the meet-in-the-middle algorithm in cryptanalysis. On average, it requires at most $O(kq^k)$ multiplications, compared with $O\left(\binom{n}{k-1} q^{k-1} k^3\right)$ multiplications for generic exhaustive search. Applying the proposed algorithm to several known families of MDS codes, including elliptic-curve, twisted Reed--Solomon, column-twisted Reed--Solomon, cyclic, and missing-monomial MDS codes over fields of order at most $32$, we obtain new MDS codes of increased lengths that remain inequivalent to Reed--Solomon codes. In particular, we construct $[9,4,6]$ codes over $\F_9$ and $\F_{13}$, each with Schur-square dimension $9$. Over $\F_{17}$, we obtain two inequivalent $[10,4,7]$ codes with Schur-square dimensions $9$ and $10$, respectively. The latter is the dual of an extended $[10,6,5]$ code, demonstrating that the method also applies when $k>n/2$. For these dimension-four codes, the Schur-square dimensions $9$ and $10$ exceed both that of RS code (Schur-square dimension $7$) and those of specific elliptic-curve and column-twisted Reed--Solomon families (Schur-square dimension $8$). Some of these parameters of non-RS MDS codes have not been reported before.
Hermitian rank-distance codes constructed using skew polynomial rings
New Maximum Hermitian $d$-Codes and New Invariants from Skew Polynomial Rings
Abstract: Maximum rank-distance codes were introduced independently by Delsarte (1978) and Gabidulin (1985) for unrestricted matrix spaces, and their study was subsequently extended to the classical form spaces of alternating, symmetric, and Hermitian matrices. For Hermitian $d$-codes, Schmidt (2018) established the upper bound and constructed optimal additive codes for all admissible parameters except when $n$ and $d$ are both even and $4\le d\le n-2$. We settle this final open existence case, more generally, construct additive maximum Hermitian rank-metric codes for every admissible length and minimum distance. Rather than working directly in the space of Hermitian matrices, we construct our objects within central simple algebras with unitary involution arising from quotients of skew polynomial rings. We also introduce scalar-field and Lyapunov operators in these algebras, leading to new invariants for the equivalence of additive Hermitian codes. Explicitly determining these invariants yields strong necessary conditions for Hermitian equivalence and demonstrates that our construction contains a large number of pairwise inequivalent codes.
Binary error correcting codes achieve higher data protection limits
Four New Single-Error-Correcting Binary Codes
Abstract: We construct a $(16, 3072, 3)$-code, a $(17,6144,3)$-code, an $(18,12288,3)$-code and a $(19,24576,3)$-code. Consequently, we get four new lower bounds: $A(16,3) \geq 3072$, $A(17,3) \geq 6144$, $A(18,3) \geq 12288$ and $A(19,3) \geq~24576$. Each of the codes consists of a union of cosets of a linear code. The constructions are the result of a computer search executing a tabu search algorithm.
Construction of new error correcting codes from special field extensions
On MRD constacyclic codes over inseparable field extensions
Abstract: In this paper, we construct MRD constacyclic codes of length $p$ over an inseparable field extension $L/K$, where $K$ has characteristic $p$. In particular, these codes cannot be obtained from known constructions.
LLM-based text compression sped up 19 times on NVIDIA GPU
High-Throughput LLM-Based Compression and What It Takes: A Systems Study of Inference Engines and Entropy Coding Optimizations
Abstract: Large language models are attractive text compressors because next-token probabilities can be converted into code lengths. In practice, however, the main bottleneck is often not modeling quality but systems cost: a compressor must obtain logits quickly enough to compete with strong classical baselines. This paper examines systems optimizations for LLM-based compression, including multistream pipelined arithmetic coding and target-interval capture, and evaluates their trade-offs across inference engines, configurations and datasets. We evaluate LLM-based text compression on three different inference engines: Transformers, vLLM, and TensorRT-LLM. Notably, we obtain a speedup of 18.84x compared to prior work's Transformers implementation and a maximum recorded inference speed of 181 kilobytes per second at a compression ratio of 7.17, when running on an NVIDIA A100.
RPA decoding needs fewer projections for structured errors
RPA Decoding with Few Subspace Projections for Correcting Structured Error Patterns in RM Codes
Abstract: The Recursive Projection Aggregation (RPA) decoder for Reed-Muller codes uses, in its default implementation, all one-dimensional subspaces at each level of recursion. We restrict our attention to the case where the number of errors is $t<d_{\mathrm{min}}/2$. It is known that if the number of errors is $t<d_{\mathrm{min}}/2$, then $2t+1$ subspaces at each level of recursion are sufficient to correct these errors. We show that, for structured error patterns, the number of subspaces required for correction can be reduced further by appropriately selecting the subspaces used for projection. In particular, when errors occur as a single burst of length $t < d_{\mathrm{min}}/2$, three subspaces at each level of recursion suffice for correction. We obtain similar results for multiple bursts and other structured error patterns as well.
Bounds for changing codes without full decoding help nonlinear coding
Entropy/Length Profile Bounds for the Conversion of (Non)linear Codes in the Merge Regime
Abstract: Code conversion changes the parameters of encoded data while avoiding complete decoding and re-encoding. Existing general bounds largely rely on the algebraic structure of linear codes. This paper develops an information-theoretic framework for nonlinear code conversion in the merge regime. Using the entropy/length profile (ELP), we derive upper bounds on the number of unchanged symbols and lower bounds on the number of read symbols for arbitrary $(n,M)_q$ codes, without assuming linearity or requiring $\log_q M$ to be an integer. We also obtain joint bounds for multiple initial codes and consequences involving minimum distance. For linear codes, the proposed bounds reduce to the corresponding generalized Hamming weight (GHW) bounds. The construction based on Hamming codes converts Hamming codes of redundancy two into a Hamming code of any larger redundancy and simultaneously attains the general bounds on unchanged and read symbols. The construction based on quasigroups shows that new bounds remain tight for genuinely nonlinear codes of nonintegral dimension and at a nonintegral entropy threshold, which, to the best of our knowledge, is the first construction of convertible codes for nonlinear codes.
Privacy tradeoffs found in dna data retrieval from multiple servers
Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage
Abstract: As DNA-based data storage evolves, protecting user privacy during data retrieval has become increasingly important. We study sequential random sampling DNA private information retrieval (SRS DNA PIR) with multiple colluding random sampling servers, where the database is partitioned into servers of equal size. We investigate the tradeoff between the download cost, defined as the expected number of queries, and the privacy leakage, measured by mutual information. We derive lower bounds on this tradeoff, including a bound given by an optimization problem. This bound is tight when each server stores two files, and we construct schemes that attain it. For servers of any size, we construct schemes that apply a single-server scheme to a randomly selected subset of servers.
Multi view linear programming improves bounds on locally recoverable codes
Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability
Abstract: We develop a multi-view linear-programming framework for locally recoverable codes with arbitrary fixed availability $a$. For any retained order $1 \le s \le a$, the selected helper sets, the recovered coordinate, and their complement form an $(s+2)$-part partition. Recording the Hamming distance on all blocks preserves both compatibility among the selected repair alternatives and their coupling with the remaining coordinates. The resulting joint distribution satisfies centered counting identities, product-Krawtchouk positivity, and collision inequalities from the local-distance condition; for fixed $s$, these constraints give a polynomial-size relaxation for arbitrary, possibly nonlinear, codes over any finite field. Retaining one view recovers the three-block model of our companion paper. We develop the first genuinely multi-view case, $s=2$, in detail and specialize the exact computations to availability $a=2$. The resulting four-block LP projects to both the one-view three-block model and a globally conditioned two-view relaxation, making explicit the information lost by each coarsening. Exact rational primal-dual certificates together with checked constructions prove $M_{\max}(2,8,4,2,2,2)=8$, $M_{\max}(3,7,3,2,2,2)=27$, and $M_{\max}(4,7,3,2,2,2)=64$; in all three cases the four-block bound is strictly stronger than both coarsenings.
Efficient data compression using diffusion language models and hypernetworks
HyperZip: Efficient Data Compression through Personalized Diffusion LLMs with Hypernetworks
Abstract: Large language models (LLMs) have shown strong potential for lossless data compression, but existing approaches are constrained by the high computational cost and low throughput of autoregressive decoding. We propose HyperZip, an efficient and scalable LLM-based compression framework that leverages diffusion-based LLMs (dLLMs) with Multi-Token Prediction (MTP) to accelerate LLM-based data compression processes. We identify a trade-off in diffusion-based compression, where increasing decoding throughput degrades the compression rate. To mitigate this trade-off, HyperZip employs a hypernetwork to generate data-specific updates from a context representation, adapting the dLLM to the target data without costly fine-tuning, resulting in a low compression rate and high throughput. Extensive experiments show that HyperZip achieves a superior trade-off between compression rate and speed compared with state-of-the-art baselines.
A proof confirms a key inequality in error-correcting codes
A proof of the generalized packing-covering conjecture
Abstract: The generalized packing--covering conjecture of Elimelech, Firer and Schwartz asserts that, for every linear code $\mathcal{C}$ and every admissible order $t$, the $t$-th generalized Hamming weight $d_t(\mathcal{C})$ and the $t$-th generalized covering radius $R_t(\mathcal{C})$ satisfy $d_t(\mathcal{C})\le 2R_t(\mathcal{C})+2$. We give a computer-assisted proof of the conjecture for every linear code over every finite field and every admissible order. Combining a parity-check reformulation of the conjecture, bounds on the length of putative counterexamples, and successive puncturing arguments, we settle all orders $t\ge 32$ and reduce the remaining orders to finitely many parameter tuples, which we exclude by an exact computer verification.
Lower bounds improve understanding of error correction with deletions
Lower Bounds for all List-Decodable Deletion Codes
Abstract: A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.
Spatially coupled codes require smaller seed regions to start decoding
Threshold Saturation from a Bounded Region in Multidimensional Spatially Coupled Codes over the BEC
Abstract: We prove that a bounded shortened region initiates decoding throughout multidimensional spatially coupled regular LDPC and MacKay--Neal (MN) codes over the binary erasure channel (BEC). In every fixed finite dimension, uniform hypercube coupling permits the coupling width and shortened region to be chosen independently of the total number $V$ of spatial positions. At fixed widths and dimension $d>1$, replacing a shortened slab by a bounded hypercube reduces the shortening fraction from order $V^{-1/d}$ to order $V^{-1}$, with the same improvement in the shortening term of the check-count rate bound. Regular LDPC codes decode below their uncoupled potential threshold. MN codes achieve capacity for every integer degree choice $\ell>r\geq2$, $g\geq2$: their actual transmitted rates tend to $r/\ell$ and their average bit-erasure probabilities under sum-product decoding vanish below $1-r/\ell$. The proof combines an endpoint-potential identity, removal of an auxiliary constraint, finite-time estimates uniform in direction, and a curvature comparison that transfers flat-boundary progress to expanding balls. For MN codes, elementary inequalities establish fixed-point positivity for all these degrees. Two-dimensional density-evolution examples illustrate the dependence on the initial shortened region; the general sufficient constants are not evaluated numerically.
Upper bounds refined for codes with fixed symbol weights and compositions
Envelopes of upper bounds for nonbinary constant-weight and constant-composition codes
Abstract: Deriving upper bounds on code size from existing bounds is a classical approach in coding theory, dating back to the seminal results of Elias, Bassalygo, and Levenshtein. We study a framework encompassing the Bassalygo--Elias and Levenshtein inequalities for binary and nonbinary (constant-weight) codes and provides certain generalizations. The asymptotic cost of transferring a bound between different symbol compositions is expressed in terms of mutual information, yielding an information-theoretic optimal transport formulation. We determine the optimal permutation-transport cost between arbitrary compositions in terms of their least common majorant in the majorization order. Specializing to symmetric constant-weight compositions yields explicit transport profiles. As a byproduct, we establish unimodality of the asymptotic constant-weight rate as a function of the relative weight. We prove that the resulting closure operators are idempotent and that applying transport before outer Bassalygo--Elias averaging leaves the unrestricted bound obtained from the same input unchanged. We also establish necessary and sufficient conditions for an upper bound to be a fixed point of the closure operator. Since the asymptotic rate function is an upper bound for itself and it is a fixed point, we conclude the Schur concavity of the constant-composition rate function. Finally, we survey existing upper bounds for binary and nonbinary constant-weight and constant-composition codes, combine them into optimized envelopes within the transport framework, and obtain improved theoretical and numerical bounds.
Binary deletion channel capacity approximated within one hundredth bit
Binary Deletion Channel Capacity to Within One Hundredth of a Bit
Abstract: The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.
Hyper-derivative algebraic geometry codes extend error correction possibilities
Hyper-derivative Algebraic Geometry Codes via Local Expansions
Abstract: In this paper, we develop a systematic construction framework of hyper-derivative algebraic geometry codes via local expansions, extending hyper-derivative Reed-Solomon codes from the rational function field to general algebraic function fields. Using the residue theorem, we determine their Euclidean duals and illustrate that the duals naturally reverse. We further give criteria for reverse self orthogonality and reverse self duality in terms of two classes of bilinear forms. Finally, we provide an asymptotic bound on the rate and relative distance via function field towers.
Twisted Roth-Lempel codes offer new error correction options
On Twisted Roth-Lempel Codes
Abstract: In 1989, Roth and Lempel constructed a well-known family of non-Reed-Solomon maximum distance separable (MDS) codes. For decades, this family of codes has attracted extensive research attention due to its algebraic structure, low-complexity decoding, and broad applications in cryptography and data storage. In this paper, we present a class of twisted Roth-Lempel codes. We investigate their minimum distance, MDS and NMDS properties. Specifically, we determine the necessary and sufficient conditions for the TRL codes to have minimum distance n-k or n-k+1. Furthermore, we determine the necessary and sufficient conditions for the TRL code to be an MDS or NMDS code. Moreover, we show that the dimension of the Schur square of the TRL code is at least 2k+1, and thus the TRL code is a non-RS code inequivalent to the corresponding RL code.
Polynomial time algorithm improves error correction for Reed-Solomon codes
Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
Abstract: We give a deterministic polynomial-time list-decoding algorithm for Reed-Solomon codes over prime fields that approaches list-decoding capacity for every evaluation set and every constant rate.