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:2605.08973

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

Zhengyi Jiang, Wenhao Liu, Zhongyi Huang, Bo Bob Bai, Gong Zhang, Hanxu Hou

Published May 9, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2605.08973

Related papers

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

Zhengyi Jiang, Wenhao Liu, Zhongyi Huang +1 more

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

arXiv:2608.08171•Aug 8, 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

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

Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4 more

We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $Θ(n^{-1/2})$ requires $Ω(n)$ membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within $Θ(n^{-3/2})$ distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real $n\times n$ matrix requires at least $n/2$ matrix-vector product queries. The construction also yields an $Ω(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $Θ(n^{-2})$. These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an $Ω(\min\{\sqrtκ,n\})$ gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and $κ$-smooth functions, which is optimal up to a logarithmic factor.

quant-pharXiv:2609.09035•Sep 9, 2026•0 citations

On the Insdel Error-Correcting Capacities of Binary Reed–Muller Codes and Simplex Codes

Runqing Qiu, Shixin Zhu, Yang Li +1 more

Insertion-deletion (insdel for short) codes have received extensive attention due to their ability to correct synchronization errors. It is usually a very challenging problem to determine the insdel distances of linear codes. In this paper, a good lower bound on the insdel distance of a linear code with a certain algebraic structure is provided and it indeed gives an affirmative answer to an open problem proposed by Hao Chen (IEEE Transactions on Information Theory, 68(8): 5126–5132, 2022). Applying this lower bound to binary first-order Reed-Muller codes and binary simplex codes, we obtain that they possess linear subcodes that can correct arbitrary insdel errors while maintaining Hamming distances robustness. The application of this bound on Reed-Muller codes completely solves an open problem left by Lara Dolecek and Venkat Anantharam (IEEE Transactions on Information Theory, 53(4): 1430–1443, 2007). In order to enhance the code rate, we further perform puncturing on these subcodes and determine the Hamming distances of the punctured subcodes while ensuring that their insdel distances remain unchanged.

IEEE Transactions on Information Theory•Feb 13, 2026•0 citations

From Bit to Block: Decoding on Erasure Channels

Henry D. Pfister, Oscar Sprumont, Gilles Zémor

We provide a general framework for bounding the block error threshold of a linear code$C \subseteq \mathbb{F}_{2}^{N}$over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of any$r$-dimensional subcode of$C$, for all small values of$r$. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.

arXiv:2501.05748•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations
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.
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
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.
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.
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of nnn-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error Θ(n−1/2)Θ(n^{-1/2})Θ(n−1/2) requires Ω(n)Ω(n)Ω(n) membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within Θ(n−3/2)Θ(n^{-3/2})Θ(n−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n×nn\times nn×n matrix requires at least n/2n/2n/2 matrix-vector product queries. The construction also yields an Ω(n)Ω(n)Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n×nn\times nn×n matrix to additive accuracy Θ(n−2)Θ(n^{-2})Θ(n−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min⁡{κ,n})Ω(\min\{\sqrtκ,n\})Ω(min{κ​,n}) gradient-query lower bound for constant-accuracy optimization of 111-strongly convex and κκκ-smooth functions, which is optimal up to a logarithmic factor.
Insertion-deletion (insdel for short) codes have received extensive attention due to their ability to correct synchronization errors. It is usually a very challenging problem to determine the insdel distances of linear codes. In this paper, a good lower bound on the insdel distance of a linear code with a certain algebraic structure is provided and it indeed gives an affirmative answer to an open problem proposed by Hao Chen (IEEE Transactions on Information Theory, 68(8): 5126–5132, 2022). Applying this lower bound to binary first-order Reed-Muller codes and binary simplex codes, we obtain that they possess linear subcodes that can correct arbitrary insdel errors while maintaining Hamming distances robustness. The application of this bound on Reed-Muller codes completely solves an open problem left by Lara Dolecek and Venkat Anantharam (IEEE Transactions on Information Theory, 53(4): 1430–1443, 2007). In order to enhance the code rate, we further perform puncturing on these subcodes and determine the Hamming distances of the punctured subcodes while ensuring that their insdel distances remain unchanged.
We provide a general framework for bounding the block error threshold of a linear codeC⊆F2NC \subseteq \mathbb{F}_{2}^{N}C⊆F2N​over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of anyrrr-dimensional subcode ofCCC, for all small values ofrrr. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.