CS Paper Radar

Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality

Aryeh Lev Zabokritskiy

cs.IT math.CO ·submitted 2026-09-01 16:09 UTC · v3

Abstract

Codes over graphs store symbols on edges of a complete undirected graph on $n$ vertices with a self-loop at each vertex; erasing a node removes all its incident edges. Extending Yohananov, Efron, and Yaakobi's construction, we obtain binary codes correcting any three node erasures at infinitely many prime lengths $n$, unconditionally, with redundancy $3n-2$, one bit above the graph Singleton bound. The earlier construction has the same redundancy but requires $2$ to be primitive modulo $n$, which is not known for infinitely many primes. We give a deterministic decoder for these triple-node codes using $O(n^2)$ binary operations and construct Singleton-optimal binary triple-node codes at $n=6,8,10,12$. When $2$ is primitive modulo an odd prime $n$, we extend their double- and triple-node codes to binary codes correcting $ρ$ node erasures with redundancy $ρn-(ρ-1)$ for $2\leqρ\leq(n+1)/2$, saving $ρ-1$ bits over the binary symmetric rank-metric construction when $ρ<(n+1)/2$. Over every finite field of size $q$, the node weight of a word is the least number of vertices whose erasure removes its support. We give exact formulas for ball volumes in this node metric and prove that, for fixed $q,t$, the radius-$t$ volume is asymptotic to $\binom nt q^{tn-\binom t2}$ as $n\to\infty$. We obtain existence and covering bounds; for fixed $q,ρ$, we show that linear $ρ$-node-erasure-correcting codes exist with redundancy at most $ρ\log_q n+O_{q,ρ}(1)$ above the graph Singleton bound. Finally, reformulating Yohananov and Yaakobi's criterion, we show that a linear code over any finite field is Singleton-optimal for $ρ$ node erasures if and only if its dual is Singleton-optimal for erasures of the coordinates inside any $n-ρ$ vertices.

Comment
44 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal single-track Gray codes from Gray-ordered necklaces

cs.DM math.COcs.IT ·2026-10-17 ·Chris Dzoba
code/data similarity 0.66
Abstract · 7 pages, 1 table. Ancillary files: Lean 4 formalization, construction and verification programs, the codes for n <= 23, and verification log…

A single-track Gray code of length $n$ is a cyclic Gray code of $n$-bit words in which every column is a cyclic shift of the first. For prime $n$ the longest possible period is $2^n-2$. Whether it is attained for every prime has been open since Hiltgen, Paterson and Brandestini introduced these codes in 1996, and optimal codes were known for primes $n\le 19$. We show that a conjecture of Degni and Drisko (2007) on the reflected Gray code order of necklaces implies optimal single-track Gray codes for every prime. Their list of necklaces, conjecturally a Gray path for prime $n$, closes into a Hamilton cycle of the necklace graph after $(n-3)/2$ explicit Pósa rotations, and such a cycle lifts to an optimal code. This implication is formalized in Lean 4. Together with computation it gives optimal single-track Gray codes for every odd prime $n\le 47$: for $n\le 37$ explicit codes checked word by word by a program independent of the generator, and for $n=41$, $43$ and $47$ codes obtained from the implication after the Degni-Drisko property was verified at these lengths by two independently written programs.

0.28

The Multiple Unicast Conjecture is False

cs.IT cs.CCcs.DMcs.DS ·2026-10-07 ·Mark Braverman, Zhongtian He
theoryhighly cited similarity 0.66
Abstract

The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.

0.39

On the Vertices That Belong to All Minimum Identifying Codes

cs.DM math.CO ·2026-09-09 ·Ville Junnila, Tero Laihonen, Havu Miikonen
theory similarity 0.64
Abstract

Identifying codes in graphs have been widely studied since their introduction by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we consider the vertices that are in every minimum identifying code in a graph. There are two types of such vertices: \emph{always-forced} vertices that belong to all identifying codes (minimum or not) and \emph{min-forced} vertices that belong to all minimum identifying codes. A vertex is called \emph{proper-min-forced} if it is min-forced but not always-forced. We show an upper bound $2n/3$ for the number of such proper-min-forced vertices in a closed-twin-free graph of order $n$. Moreover, for integers $n$ divisible by three, we construct an infinite family of graphs in which there are $2n/3-1$ such vertices. In addition, we determine the maximum number of edges in a graph of even order such that the graph contains proper-min-forced vertices. We also show that the decision problem of determining whether a given vertex in a graph is proper-min-forced is co-NP-hard.

0.20

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

cs.IT ·2026-09-29 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.64
Abstract · 52 pages

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

0.12

Cyclic triorthogonal codes in prime dimension

cs.IT quant-ph ·2026-10-06 ·Shiroman Prakash
theorycode/data similarity 0.62
Abstract · 24 pages, 2 tables. Code and data: https://github.com/spdei/cyclic-triorthogonal-codes

We study cyclic triorthogonal codes in prime dimension $p$, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd $p$, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to $p$, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for $p=3$ up to length $121$ and $p=5,7$ up to length $96$. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length $763$. For qudits, we find codes such as $[[19,1,3]]_3$ and $[[7,1,3]]_7$, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of $[[p,1,2\lfloor p/6\rfloor+1]]_p$ codes.

0.51

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

cs.IT cs.CCmath.CO ·2026-11-02 ·Oliver Janzer, Peter Manohar
theory similarity 0.62
Abstract

We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{Ω(\sqrt{k})}$. This improves on the prior best lower bound of $2^{Ω(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length $n = 2^{O(\sqrt{k})}$, is optimal up to constant factors in the exponent. Our proof builds on the approach of [KM24a], further refined in [Yan24,KM24b], that uses "chain derived equations" in combination with Kikuchi graphs. The crux of our argument is to show that a certain edge-coloured Kikuchi graph has a unique colour cycle: a cycle in which some colour is used exactly once. We do this by controlling the distribution of colours at each vertex in the graph using a random walk mixing argument and a novel hypergraph decomposition based on edge expansion of the hypergraph's "flattening" into a graph.

0.42

The weight enumerators of irreducible cyclic codes of length $2^\ell$

cs.IT math.CO ·2026-10-08 ·Ricardo A. Podestá, Denis E. Videla
similarity 0.61
Abstract · 19 pages, 3 tables

Using the spectral relation between irreducible cyclic codes (ICC) and generalized Paley (GP) graphs recently found by the authors, we study the weight distribution of irreducible cyclic codes of length $2^\ell$, $\ell \in \mathbb{N}$. These codes were previously studied by Sharma, Bakshi and Raka, who divided them into two families (each having two cases). First we characterize the GP-graphs spectrally related to these families of ICCs: they are complete, semiprimitive, Hamming, or Cartesian products of semiprimitive GP-graphs. We then compute the spectrum of these graphs and hence, by the mentioned spectral relation we finally obtain neat explicit expressions for the weight enumerators of all the irreducible cyclic codes of length $2^\ell$ with $\ell \in \mathbb{N}$.

0.11

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.60
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04