CS Paper Radar

Quadratic bounds for uncompletable words and matrix mortality

Rahul Chandelkar, Samrath Singh Chadha

cs.FL math.CO ·submitted 2026-09-25 04:54 UTC · v2

Abstract

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

Comment
Lean formalization and implementation pilot included as ancillary material

Closest papers

Nearest neighbours by meaning across the whole index.

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.71
Abstract

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth $k-1$, is either identically zero or nonzero on a word of length at most $2k-3$. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are $k-1$ and $k$, we prove the sharper bound $2(k-1)^2-1$ and characterize equality. The binary code with the single short word $a^{k-1}$ attains this bound for every $k\ge2$; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

0.12

CPM-LDPC Codes Attaining the Minimum-Distance Bound

cs.IT ·2026-09-15 ·Kenta Kasai
theorycode/data similarity 0.69
Abstract · 13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.

0.35

New lower bounds for constant-weight codes via seeded bit-swap tabu search

cs.IT math.CO ·2026-08-14 ·William Echols
similarity 0.68
Abstract

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $τ_{32}$, $τ_{33}$, $τ_{34}$, and $τ_{37}$.

0.40

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.66
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Asymptotically Optimal Bounds for Counting Near-Minimum Circuits in Regular Matroids

cs.DM math.CO ·2026-11-11 ·Robert P. Streit
theory similarity 0.66
Abstract · 28 pages

For a regular matroid on $m$ elements with positive weights and weighted girth $g_w$, we prove that the number of circuits of weight at most $αg_w$ is bounded by $(Km)^{2α}$, for every real $α\ge1$ and an absolute constant $K$. This improves the previous $m^{O(α^2)}$ bound of Gurjar and Vishnoi and matches classic graph cut and cycle counting bounds of Karger and Subramanian. We also show this is asymptotically optimal for all real $α\geq 1$ under the Erdős girth conjecture, while unconditional optimality holds for half-integer $α$ by prior results. As consequences, we resolve a recent conjecture by Khanna, Putterman, and Song implying the existence of a parallel basis search algorithm for regular matroids terminating in logarithmically many rounds of independence queries, and obtain improved bounds on the number of near-minimum weight codewords in regular codes and near-shortest vectors in totally unimodular lattices under $\ell_p$-norms.

0.23

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.65
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Quantum Černý complexity of binary words

cs.DM quant-ph ·2026-09-30 ·Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen
theory similarity 0.65
Abstract

We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start state $ρ_0$ such that $w$ is the unique shortest word whose associated channel is constant on the reachable set. We show that $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{qcp}$ in which the synchronization target is required to be a pure state. We prove that in dimension $2$ no word of length at least $2$ can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving $\mathrm{qcp}(01^n0)=3$ with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.

0.28

Optimal Labeling Schemes for $Γ$-Free Matrices

cs.DS ·2026-10-21 ·Sankardeep Chakraborty, Seungbum Jo
theory similarity 0.65
Abstract

We study labeling schemes for $p \times q$ $Γ$-free binary matrices, which do not contain a submatrix of the form $Γ= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. We give a labeling scheme that uses $O(\log^2 N)$-bit labels for rows and columns, where $N=p+q$, such that any matrix entry can be determined from the corresponding two labels in constant time in the word RAM model. The worst-case label size matches the counting lower bound up to constant factors. We also show that the entrywise least $Γ$-free supermatrix of an arbitrary $p\times q$ binary matrix, together with its labels, can be constructed in $O(pq)$ time. Our construction represents a $Γ$-free matrix by a sequence of rooted forests, where each column corresponds to a node and the $1$-entries of each row form a root path in its corresponding forest. For $n$-vertex strongly chordal and chordal bipartite graphs, our result gives asymptotically optimal $O(\log^2 n)$-bit adjacency labeling schemes with constant-time queries. These results answer both representation questions posed by Spinrad in 1995.

0.21