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.

Thu 12 NovInformation TheoryDiscrete MathematicsData Structures and Algorithms
The gist
Fixing mistakes in sequences of symbols, like typos or dropped parts, is a classic challenge. The authors build special codes that can explicitly correct mixed errors of insertions, deletions, and substitutions with as little extra information as theoretically possible. They create these codes by assigning multiple ‘colors’ to parts of messages and carefully encoding these so errors can be detected and fixed efficiently. Their method comes with algorithms that can encode and decode messages with some computational cost but guarantees the lowest known overhead.
Open → 2611.16835v1

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.

Wed 11 NovDiscrete MathematicsInformation Theory
The gist
This paper deals with special sets of points in mathematical spaces where few points lie in any small sub-area. The authors provide a new, clear method to create these sets, improving previous methods that had bigger overlaps. This helps build more efficient coding systems that can recover data with fewer errors and smaller output lists. Their approach combines existing coding designs with new local sets to achieve better results. This development overcomes past limitations in constructing such coding techniques.
Open → 2611.14909v1

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.

Mon 9 NovComputational Complexity
The gist
Some codes let you fix mistakes quickly by checking only a few parts, but before, this was mostly possible over specific mathematical fields, not the real numbers. The authors found a way to create such codes over real numbers using curves that pass through points on a grid, which helps find errors by looking nearby. This challenges earlier beliefs that such quick correction codes couldn't exist over the real numbers. The method also makes sure that no part of the grid is checked too often, spreading out the work evenly.
Open → 2611.13281v1

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.

Sun 8 NovInformation Theory
The gist
The paper studies how to compress sequences of information while keeping each piece private during access. The authors show that for data coming from processes with memory (like stationary sources), you can compress efficiently while still keeping access to each piece private and accurate most of the time. However, if the source is more complex and not predictable (non-ergodic), there is a cost in compression rate to maintain this privacy. This work extends previous results that were only known for memoryless data sources.
Open → 2611.11501v1

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.

Sun 8 NovInformation Theory
The gist
Hash codes and list-recoverable codes help computers organize and retrieve data efficiently. This paper shows improved results that beat previous probabilistic limits on how well these codes can perform. It also advances understanding of trifferent codes, a special kind of code useful for unique data encoding. The improvements hold true for various code sizes and recovery parameters, indicating stronger coding strategies are possible.
Open → 2611.11262v1

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.

Fri 6 NovInformation Theory
The gist
Magnetic tape storage needs very reliable data correction to keep information safe. The authors present a new way to decode data using a special kind of Reed-Solomon error correction code that can fix many errors even when the raw error rate is quite high. They improve how the decoder handles tricky cases where errors could cause confusion or get stuck. Their method keeps running decoding steps until no more changes happen, which reduces errors significantly while working efficiently on normal laptops and has designs for faster hardware use.
Open → 2611.09366v1

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.

Thu 5 NovInformation TheoryComputational Complexity
The gist
Random linear codes are used in computer science to encode data. This paper shows that for many local properties—those depending on a small set of codewords—the chance that a random code has the property changes abruptly around a specific code size. The authors prove that this threshold is closely predicted by a simple mathematical estimate called the expectation threshold. They also show this insight works not just for fully random codes but for certain pseudorandom codes too, expanding its usefulness to more practical coding schemes.
Open → 2611.07661v1

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.

Tue 3 NovComputational ComplexityInformation Theory
The gist
This work investigates how efficiently error-correcting codes can allow quick data retrieval even when some data is damaged. The authors show that to maintain these fast checks, the overall code length must grow at least a certain amount, nearly matching previously known upper limits. They handle more general code types with adaptive methods, improving our understanding of the trade-offs involved. Their approach uses a new mathematical tool called the capped Horvitz–Thompson estimator to analyze these decoding methods.
Open → 2611.04678v1

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.

Mon 2 NovInformation Theory
The gist
It's hard to fix messages that get changed by mistakes like missing or extra bits. This paper shows how to create special codes that can correct a fixed number of these errors while keeping extra information small. The authors developed methods to build, send, and fix these codes quickly using algorithms. Their approach matches the best theoretical guarantees without trying every possible message.
Open → 2611.04023v1

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$.

Sun 1 NovInformation Theory
The gist
This paper looks at ways to fix errors in messages where some parts have been swapped right next to each other, called adjacent transpositions. The authors show how to build long codes by joining together multiple smaller blocks that can each be independently encoded and decoded. Their methods let you check for errors efficiently by testing only a fixed number of blocks, no matter how long the message is. They provide detailed constructions for binary codes that use close to the least extra bits possible and work quickly. The work also proves some limits on how much of a message needs to be seen to recover earlier parts reliably.
Open → 2611.02192v1

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$.

Sun 1 NovInformation Theory
The gist
The authors developed a special kind of error-correcting code called MDS (maximum distance separable) codes using mathematical objects called hyperelliptic curves. These codes have lengths approximately the square root of the size of the alphabet used, which is unusual compared to existing codes. Their codes achieve optimal error correction parameters and are distinct from traditional Reed–Solomon codes when the alphabet size gets large enough. This work provides new ways to design codes that could improve data transmission and storage reliability.
Open → 2611.01546v1

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.

Fri 30 OctInformation Theory
The gist
This paper studies how much information multiple users need to send so a server can compute a certain combined value without error. It focuses on a small, basic case where users observe some linear relationships of common data, and the server wants another linear combination. The authors show that the minimum communication needed depends on a geometric property called the cross-ratio of four lines, not just on basic dimensions of the data. They also find different communication limits depending on the prime number underlying the data field and the specific linear combination the server wants.
Open → 2610.42023v1

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.

Thu 29 OctMachine Learning
The gist
Storing large sets of data arranged in many dimensions can require a lot of space. The authors created TensorSSM, a new way to shrink this data that keeps better track of where data points sit across different dimensions. Instead of squishing all the data into one line, TensorSSM remembers spatial relationships at various levels and between different dimensions. This approach helps keep more detail and leads to better accuracy and smaller storage needs across many types of data.
Open → 2610.40871v1

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.

Wed 28 OctInformation TheoryCryptography and Security
The gist
This work improves understanding of certain properties of error-correcting codes, which help computers fix errors in data. The authors build on earlier research to show that several complex code types behave similarly when decoding curves, a method important for verifying data efficiently. They also reduce how large the set of symbols (alphabet) needs to be for these codes to work well, making them more practical. This helps improve techniques used in very efficient proofs for checking computations.
Open → 2610.38862v1

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.

Wed 28 OctInformation Theory
The gist
Random access codes compress information but still let you recover any piece you want better than random guessing. The authors clarify what makes such codes good when data grows large and show how to build them efficiently. They use special linear codes that let you decode parts of compressed data with a guaranteed success rate. Their constructions work well for large data and come with practical algorithms to create these codes.
Open → 2610.38429v1

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.

Mon 26 OctInformation Theory
The gist
Sometimes, when sending secret information, an eavesdropper can sneak a peek at small parts of two related secret codes. This paper looks at special codes called secure convertible codes that keep information safe even if some pieces are seen. The authors build two types of these codes: one that works for all situations but needs big mathematical spaces, and another that is easier to use but works only in certain scenarios. These codes help keep data secure when it is changed or combined in specific ways.
Open → 2610.34863v1

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).

Thu 22 OctComputational Complexity
The gist
Reed-Solomon codes are a way to detect and fix errors in data, like when files get corrupted. Usually, there is a known limit called the Johnson bound on how many errors these codes can fix efficiently. The authors found a way to build these codes deterministically (with a fixed method rather than randomness) so they can fix even more errors than before, while still being practical to construct. Their approach uses connections to other mathematical problems and runs in reasonable time for large data sizes.
Open → 2610.31922v1

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.

Thu 22 OctInformation Theory
The gist
The paper looks at a broad family of error-correcting codes used to protect data stored or sent across noisy channels. The authors identify a mathematical structure that links several well-known codes together, like Reed-Solomon and Gabidulin codes, by using special kinds of polynomials. They show how to describe these codes' sizes and minimum error-correcting ability exactly, extending to settings with multiple variables and different code shapes. This generalization helps understand and design new codes that balance different error models.
Open → 2610.31358v1

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.

Thu 22 OctInformation Theory
The gist
This work finds a way to make certain special error-correcting codes, called MDS codes, longer while keeping their unique structure different from common Reed–Solomon codes. The authors created a practical step-by-step method that does this extension faster than previously possible. They tested their method on several known kinds of these codes and successfully produced new longer codes with properties not seen before. These extended codes could be useful for data transmission and storage where very reliable error correction is needed.
Open → 2610.31023v1

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.

Mon 19 OctInformation Theory
The gist
Hermitian rank-distance codes are special arrangements of matrices used in error correction and data storage. Before this work, some configurations of these codes were not known to exist, especially when certain parameters were even numbers. The authors solved this last piece by building these codes in a new mathematical space called skew polynomial rings, which helps manage complex symmetries. They also introduced new tools to tell when two codes are essentially the same or different, showing their solutions offer many unique options.
Open → 2610.26048v1

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.

Fri 16 OctInformation Theory
The gist
Finding ways to protect data from mistakes during transmission or storage is important, and error-correcting codes help with this by detecting and fixing errors. This paper presents four new codes that improve the known limits on how many error-free messages can be sent using certain binary codes that fix single errors. The new codes were discovered by the authors using computer-based search methods. These advances help understand the capabilities of error-correcting codes in securing digital information.
Open → 2610.23626v1

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.

Fri 16 OctInformation Theory
The gist
Some error-correcting codes, which help fix mistakes in data, come from known rules about certain mathematical fields. This paper finds a new way to build a particular type called MRD constacyclic codes using unusual fields where usual rules don’t apply. These new codes are different and can’t be created by earlier methods. The authors show how to do this for code lengths related to the prime number that defines the field's behavior.
Open → 2610.23459v1

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.

Tue 13 OctDatabases
The gist
Compressing text means making it take up less space, often by predicting the next word to save data. Large language models (LLMs) can do this well, but they are usually slow and costly to use for real-time compression. The authors studied how to make LLM-based text compression much faster by improving both the software that runs the models and the method of encoding. They tested three different ways to run these models and achieved an 18.84 times speed increase compared to previous methods, reaching a high compression rate while running on an Nvidia A100 graphics card.
Open → 2610.17586v1

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.

Mon 12 OctInformation Theory
The gist
Reed-Muller codes help fix mistakes in digital data, but decoding them can be slow because it looks at many parts. The authors found that when the errors follow a pattern, like a burst of mistakes in a row, the decoder can check fewer parts yet still fix all errors. This makes decoding potentially faster and more efficient for these special cases. Their work shows how picking which parts to check carefully can reduce the effort needed to correct data.
Open → 2610.16240v1

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.

Sun 11 OctInformation Theory
The gist
Sometimes when you have encoded (compressed or protected) data, you want to change how it's encoded without fully decoding and re-encoding it. Existing methods mostly work only for special 'linear' codes. This paper by the authors creates a new way to understand and limit how much of the code you need to read or keep the same when changing between arbitrary codes, including nonlinear ones. They also show examples where their limits are as tight as possible, even for nonlinear codes.
Open → 2610.15252v1

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.

Wed 7 OctInformation Theory
The gist
DNA data storage is a new way to save information by encoding it in DNA molecules. The authors studied how to keep a person's data requests private when retrieving information from several servers that store DNA data. They figured out how much data needs to be downloaded to protect privacy and how much privacy can be lost if less data is downloaded. They also created methods that reach the best possible balance when each server holds two data files.
Open → 2610.10211v1

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.

Wed 30 SeptInformation Theory
The gist
Locally recoverable codes help store data so that lost parts can be fixed by looking at small pieces of the data. This paper improves how we measure the best possible size of such codes when multiple recovery options are available. The authors create a new mathematical method using several ‘views’ of the code’s structure that gives tighter limits than previous models. They prove these new limits with exact calculations on small example codes, showing this method gives better results than older ones.
Open → 2609.39230v1

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.

Mon 28 SeptArtificial Intelligence
The gist
Compressing data into smaller sizes normally takes a lot of computing time, especially when using advanced language models. The paper introduces HyperZip, a new method that speeds up data compression by predicting multiple tokens at once with diffusion-based language models. To keep good compression quality while speeding up, HyperZip uses hypernetworks to quickly adapt the model to the specific data without slow retraining. This approach balances fast processing with strong compression, outperforming existing methods according to their tests.
Open → 2609.36357v1

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.

Mon 28 SeptInformation Theory
The gist
There was a mathematical conjecture about certain properties of error-correcting codes, which are ways to protect information during transmission. The conjecture suggested a relationship between two measures related to how well these codes can detect and cover errors. The authors proved this conjecture for every possible code and order using a combination of mathematical tools and extensive computer checks. This settles a longstanding question in coding theory, ensuring the stated inequality always holds.
Open → 2609.34910v1

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.

Tue 22 SeptInformation TheoryDiscrete Mathematics
The gist
When some bits of data are accidentally deleted, it can be hard to know what the original message was. This paper studies codes that allow you to find a small list of possible original messages after some deletions. The authors show new limits on how large such codes can be to still work well, improving previous results and extending them to more cases. They also analyze how many common pieces two sequences can share after deletions or insertions.
Open → 2609.26650v1

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.

Mon 21 SeptInformation Theory
The gist
This paper shows that certain advanced error-correcting codes called multidimensional spatially coupled codes can start their decoding process from a very small fixed area, even as the entire code grows larger. The authors prove that making this seed region a bounded shape reduces the initial overhead needed to begin decoding, which means more efficient data transmission. They also demonstrate that one type of these codes, called MacKay--Neal codes, can achieve the best possible rates for data recovery in noisy channels. The work provides mathematical proof and examples showing how these codes improve decoding performance.
Open → 2609.24568v1

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.

Sun 20 SeptInformation Theory
The gist
Codes with specific patterns, like fixed numbers of certain symbols, are important in reliable data transmission. The authors studied and extended classic ways to calculate the maximum size of such codes. They connected these calculations to ideas from information theory and found new mathematical properties and better bounds. Their work helps us understand and improve limits on code sizes more precisely.
Open → 2609.23869v1

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.

Wed 16 SeptInformation Theory
The gist
Communicating over a channel where some bits get randomly deleted is a hard problem, and exactly how much information you can send without errors is unknown. The authors provide a highly accurate estimate of this maximum reliable rate, called the capacity, with an error smaller than one hundredth of a bit per bit sent. They use computer-assisted proofs combining clever mathematical bounds and numerical checks over every possible deletion probability. Their approach also includes complete computational details and code so others can verify or build on their work.
Open → 2609.19412v1

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.

Wed 16 SeptInformation Theory
The gist
Error-correcting codes help send information reliably over noisy channels. This paper extends a special kind of code, called hyper-derivative Reed-Solomon codes, from a simple setting to more complex algebraic curves. The authors develop new formulas to understand how these codes behave and find conditions when the codes have special symmetry properties. They also establish limits on how well these codes can perform as they grow larger using advanced mathematical tools.
Open → 2609.18098v1

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.

Tue 15 SeptInformation Theory
The gist
Error correction codes help protect data from mistakes or losses. Roth and Lempel created a special type of such codes that many use in data storage and cryptography. This paper studies a new twist on those codes, called twisted Roth-Lempel (TRL) codes, and finds exact conditions when they work best. The authors also show these new codes differ from the old ones in important mathematical ways, which might help in applications needing strong, efficient error correction.
Open → 2609.17304v1

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.

Mon 7 SeptInformation TheoryComputational Complexity
The gist
Error-correcting codes help fix mistakes in data transmissions. Reed-Solomon codes are widely used for this purpose, but correcting many errors efficiently has been challenging. The authors present a new method that can decode these codes faster and closer to their theoretical limit for any chosen parameters. This means better reliability in sending data over noisy channels.
Open → 2609.08005v1