Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.08171

Optimal Exponent of the Single-Error Correction Threshold with Fixed Redundancy for Analog Error-Correcting Codes

Zhengyi Jiang, Wenhao Liu, Zhongyi Huang, Hanxu Hou

Published Aug 8, 2026• 0 citations
arXivHTMLPDF

Abstract

Analog error-correcting codes (Analog ECCs), introduced by Roth [1], address errors in vector-matrix multiplication arising from analog noise and sparse outliers in in-memory computing. A fundamental open problem concerns the lower bound on the single-error correction threshold $Γ_2(\mathcal C)$ for real $[n,k]$ linear codes with fixed redundancy $r=n-k\geq 2$. Li et al. [2] recently established that for redundancy $r=2$, every real $[n,n-2]$ linear code $\mathcal{C}$ satisfies $Γ_2(\mathcal C)\geq \csc^2(\fracπ{2n})$, resolving an open problem in [1], and showed that, for every fixed $r \geq 2$, there exists a class of $[n,k]$ linear code $\mathcal{C}$ over $\mathbb{R}$ such that $Γ_2(\mathcal{C}) \leq O(n^{1+\frac{1}{r-1}})$. This paper proves the matching converse in [2]. For every $[n,k]$ linear code $\mathcal{C}\subseteq \mathbb R^n$ with fixed redundancy $2\leq r

DOI
10.48550/arxiv.2608.08171

Related papers

Tight Lower Bounds on The Single-Error Detection Threshold for Analog Error-Correcting Codes

Zhengyi Jiang, Wenhao Liu, Zhongyi Huang +3 more

Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of $k$ and $n$ for which every linear $[n, k]$ code $\mathcal{C}$ over $\mathbb{R}$ satisfies: $$\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}$$ Here, for any $\boldsymbol{x}\in\mathbb{R}^n$, $\mathsf{h}_1(\boldsymbol{x})$ represents the ratio between the largest and second largest absolute values of $\boldsymbol{x}$'s entries. As the simplest special case of Problem 1 (with $n-k=2$), the following problem was posed as Problem 2 in [1]: "Must every $(n-2)$-dimensional subspace of $\mathbb{R}^n$, $n$ even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least $(n/2)-1$?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary $n-k$ and Problem 2 corresponds to $n-k=2$. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where $n-k$ divides $k$. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.

arXiv:2605.08973•May 9, 2026•0 citations

On the Height Profile of Analog Error-Correcting Codes

Ron M. Roth, Ziyuan Zhu, Changcheng Yuan +2 more

In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in $\mathbb{R}^k$ are encoded into codewords of a linear $[n,k,d]$ code $C$ over $\mathbb{R}$. For prescribed positive reals $δ< Δ$, additive errors of magnitude at most $δ$ are tolerable and need no handling, yet outlying errors of magnitude greater than $Δ$ are to be located or detected. The trade-off between the ratio $Δ/δ$ and the number of outlying errors that can be handled is determined by the height profile of $C$; as such, the height profile provides a finer description of the error handling capability of $C$, compared to the minimum distance $d$, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of $C$. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of $C$ all have the same $L_2$ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.

arXiv:2602.20366•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

On Function-Correcting Codes

Rohit Premlal, Balaji Sundar Rajan

A class of codes designed to protect function evaluations of a message from errors was introduced in “Function-Correcting Codes” by Lenz et al. 2023. They provide a graphical representation for the problem of constructing functioncorrecting codes. We use this graph to get a lower bound on the redundancy required for function correction and classical error correction. For linear functions, we show that the adjacency matrix of this graph is diagonalised by tensor powers of Discrete Fourier Transform (DFT) matrices, which leads to a lower bound on redundancy. Also, we propose a version of the sphere packing bound for linear-function correcting codes. Further more, we identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight.

IEEE Information Theory Workshop (ITW)•Nov 24, 2024•4 citations

The Code Distortion Problem

Huck Bennett, Matthew Fox, Bryant Morrell

Two linear error-correcting codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$ are called linearly equivalent if there is a linear isometry mapping $\cal{C}_1$ to $\cal{C}_2$. In this work, we generalize the notion of linear equivalence and study the minimum distortion $\cal{D}(\cal{C}_1, \cal{C}_2)$ of a linear mapping between codes $\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^n$, which quantifies how similar $\cal{C}_1$ and $\cal{C}_2$ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes $\cal{C}_1$ and $\cal{C}_2$. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where $\cal{D}(\cal{C}_1, C_2) = 1$ and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is $\mathsf{NP}$-hard to approximate to within any constant factor, and that it is in $Σ_2^P$. We also give a single-exponential-time $k^2$-approximation algorithm for CDP, where $k$ is the dimension of the input codes. Furthermore, we give a single-exponential-time $\big(\frac{2k + 1}{3})^2$-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix $0 \to 0$ "norm" on subspaces.

arXiv:2607.26261•Jul 28, 2026•0 citations

Tight Lower Bound on the Error Exponent of Classical-Quantum Channels

Joseph M. Renes

A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constant$E(W,R)$which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.

arXiv:2407.11118•IEEE Transactions on Information Theory•Nov 20, 2024•7 citations

Improved bound on the error probability of fixed convolutional codes

Karin Engdahl, Dmitri V. Truhachev, Kamil Sh. Zigangirov

•Jan 1, 2001•0 citations
Analog error-correcting codes (Analog ECCs), introduced by Roth [1], address errors in vector-matrix multiplication arising from analog noise and sparse outliers in in-memory computing. A fundamental open problem concerns the lower bound on the single-error correction threshold Γ2(C)Γ_2(\mathcal C)Γ2​(C) for real [n,k][n,k][n,k] linear codes with fixed redundancy r=n−k≥2r=n-k\geq 2r=n−k≥2. Li et al. [2] recently established that for redundancy r=2r=2r=2, every real [n,n−2][n,n-2][n,n−2] linear code C\mathcal{C}C satisfies Γ2(C)≥csc⁡2(π2n)Γ_2(\mathcal C)\geq \csc^2(\fracπ{2n})Γ2​(C)≥csc2(2nπ​), resolving an open problem in [1], and showed that, for every fixed r≥2r \geq 2r≥2, there exists a class of [n,k][n,k][n,k] linear code C\mathcal{C}C over R\mathbb{R}R such that Γ2(C)≤O(n1+1r−1)Γ_2(\mathcal{C}) \leq O(n^{1+\frac{1}{r-1}})Γ2​(C)≤O(n1+r−11​). This paper proves the matching converse in [2]. For every [n,k][n,k][n,k] linear code C⊆Rn\mathcal{C}\subseteq \mathbb R^nC⊆Rn with fixed redundancy $2\leq r
Analog error-correcting codes (Analog ECCs) for approximate vector-matrix multiplication have been extensively studied as means to achieve fault-tolerant in-memory computation. The theoretical foundations for such coding schemes, particularly the characterization of their correction capabilities via the height profile, have been well established in recent literature. In this paper, we focus on the case of single-error detection Analog ECCs. Among several open problems related to this case proposed by Ron M. Roth in [1], Problem 1 asks: "Identify the values of kkk and nnn for which every linear [n,k][n, k][n,k] code C\mathcal{C}C over R\mathbb{R}R satisfies: h1(C):=max⁡c∈C∖{0}h1(c)≥⌈kn−k⌉."\mathsf{h}_1(\mathcal{C}):=\max_{\boldsymbol{c}\in \mathcal{C}\setminus{\{\boldsymbol{0}\}}}\mathsf{h}_1(\boldsymbol{c})\geq \Big\lceil \frac{k}{n-k} \Big\rceil.\text{"}h1​(C):=maxc∈C∖{0}​h1​(c)≥⌈n−kk​⌉." Here, for any x∈Rn\boldsymbol{x}\in\mathbb{R}^nx∈Rn, h1(x)\mathsf{h}_1(\boldsymbol{x})h1​(x) represents the ratio between the largest and second largest absolute values of x\boldsymbol{x}x's entries. As the simplest special case of Problem 1 (with n−k=2n-k=2n−k=2), the following problem was posed as Problem 2 in [1]: "Must every (n−2)(n-2)(n−2)-dimensional subspace of Rn\mathbb{R}^nRn, nnn even, contain a nonzero vector in which the ratio between the largest and second largest absolute values of its entries is at least (n/2)−1(n/2)-1(n/2)−1?" These problems directly pertain to the lower bounds on the single-error detection threshold for Analog ECCs: Problem 1 corresponds to arbitrary n−kn-kn−k and Problem 2 corresponds to n−k=2n-k=2n−k=2. In this paper, we provide an affirmative answer to Problem 2 and a rigorous proof using theories related to convex optimization. Furthermore, we extend our analytical method to show that the lower bound in Problem 1 is tight for the case where n−kn-kn−k divides kkk. Our results fill the gap in the lower bound theory of thresholds for single-error detection in Analog ECCs.
In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in Rk\mathbb{R}^kRk are encoded into codewords of a linear [n,k,d][n,k,d][n,k,d] code CCC over R\mathbb{R}R. For prescribed positive reals δ<Δδ< Δδ<Δ, additive errors of magnitude at most δδδ are tolerable and need no handling, yet outlying errors of magnitude greater than ΔΔΔ are to be located or detected. The trade-off between the ratio Δ/δΔ/δΔ/δ and the number of outlying errors that can be handled is determined by the height profile of CCC; as such, the height profile provides a finer description of the error handling capability of CCC, compared to the minimum distance ddd, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of CCC. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of CCC all have the same L2L_2L2​ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.
A class of codes designed to protect function evaluations of a message from errors was introduced in “Function-Correcting Codes” by Lenz et al. 2023. They provide a graphical representation for the problem of constructing functioncorrecting codes. We use this graph to get a lower bound on the redundancy required for function correction and classical error correction. For linear functions, we show that the adjacency matrix of this graph is diagonalised by tensor powers of Discrete Fourier Transform (DFT) matrices, which leads to a lower bound on redundancy. Also, we propose a version of the sphere packing bound for linear-function correcting codes. Further more, we identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight.
Two linear error-correcting codes C1,C2⊆Fqn\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^nC1​,C2​⊆Fqn​ are called linearly equivalent if there is a linear isometry mapping C1\cal{C}_1C1​ to C2\cal{C}_2C2​. In this work, we generalize the notion of linear equivalence and study the minimum distortion D(C1,C2)\cal{D}(\cal{C}_1, \cal{C}_2)D(C1​,C2​) of a linear mapping between codes C1,C2⊆Fqn\cal{C}_1, \cal{C}_2 \subseteq \mathbb{F}_q^nC1​,C2​⊆Fqn​, which quantifies how similar C1\cal{C}_1C1​ and C2\cal{C}_2C2​ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes C1\cal{C}_1C1​ and C2\cal{C}_2C2​. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where D(C1,C2)=1\cal{D}(\cal{C}_1, C_2) = 1D(C1​,C2​)=1 and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is NP\mathsf{NP}NP-hard to approximate to within any constant factor, and that it is in Σ2PΣ_2^PΣ2P​. We also give a single-exponential-time k2k^2k2-approximation algorithm for CDP, where kkk is the dimension of the input codes. Furthermore, we give a single-exponential-time (2k+13)2\big(\frac{2k + 1}{3})^2(32k+1​)2-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix 0→00 \to 00→0 "norm" on subspaces.
A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constantE(W,R)E(W,R)E(W,R)which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.