REVIEW 3 major objections 6 minor 7 references
Bivariate Linear Operator Codes
T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper proves that bivariate linear operator codes—message polynomials in two variables processed by linear operators—subsume both linear operator codes and permuted product codes, and gives a single sufficient condition under which…
desk verdict A genuine unifying framework for list-decodable codes, with a real but repairable gap in the proof of the main theorem around matrix-polynomial evaluation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central objects are bivariate linearly-extendible families L with the two matrices Mx,My, and the identity from Observation 3.3 that L(q(X,Y)p(X,Y))=q(Mx(X,Y),My(X,Y))L(p). This identity lets an interpolated polynomial Q(X,Y,u)=sum_i Q_i(X,Y)u^i be constrained pointwise by substituting Mx and My into the coefficients Q_i, which is what connects the interpolation equations to the received word. The second piece is list-composition: the pair (T,G) list-composes at A if for every G_i and every evaluation point, T(G_i(p)) at that point is a linear function of L(p) at that point, so that the same constraints apply to every message polynomial close to the received word. The third piece is the triangularity of the final recovery system: ordering message coefficients by total X-degree and then Y-degree makes the equations lower-triangular, and the diagonal entries are u times columns of Diag(G), so the distance of the code generated by Diag(G) bounds the number of free variables by ell.
What would settle it
Take a B-LELO family whose defining matrices Mx and My fail to commute and compute L(XYp) two ways: L(X(Yp))=Mx My L(p) and L(Y(Xp))=My Mx L(p); if these differ for some message polynomial p, then Observation 3.3's identity fails. Then run the interpolation equations of Section 6.1 on an instance satisfying all hypotheses of Theorem 5.2 except commutativity and check whether T(R_p)(x,y) can be nonzero on agreement points; a concrete instance with a list larger than q^ell would show the theorem as stated needs the extra hypothesis.
Extended reading notes
Core claim
A B-LO code encodes a bivariate polynomial p(X,Y) with degree in X less than t and degree in Y less than k by applying a family L=(L0,...,L_{s-1}) of linear operators on F[X,Y] and evaluating the resulting s polynomials at n points (x_i,y_i), producing n blocks of size s, for rate tk/(sn). When L is bivariate linearly-extendible, meaning there exist matrices Mx and My such that L(Xp)=Mx L(p) and L(Yp)=My L(p), the code is a B-LELO code. Theorem 5.2 states that if there are operator families G=(G0,...,G_{w-1}) and T=(T0,...,T_{r-1}) such that (T,G) list-composes in terms of L at A, G is degree-preserving, Diag(G) generates a code of distance tk-ell, and B-LELO^A_{d1,d2}(T) has distance D for some d1,d2 satisfying (d1-t+1)(d2-k+1)>nr/w, then B-LO^A_{t,k}(L) is list-decodable up to distance D with list size q^ell. The proof interpolates a polynomial Q whose coefficient count exceeds the number of constraints, shows that every close codeword forces a related polynomial to vanish at agreement points, and then solves a lower-triangular linear system whose diagonal entries are inner products of a nonzero vector with columns of Diag(G); because Diag(G) has distance tk-ell, the solution space has dimension at most ell. This recovers the univariate LO list-decoding theorem as a special case and gives a new derivation that permuted product codes are list-decodable up to capacity.
Load-bearing premise
The proof of Theorem 5.2 assumes the identity L(q(X,Y)p(X,Y))=q(Mx(X,Y),My(X,Y))L(p), which requires the matrices Mx and My to commute on every polynomial L(p); the paper states this identity without proving commutativity, and the interpolation step uses it directly, so if the identity fails for some valid B-LELO family the argument that close codewords satisfy the interpolation equations breaks.
Editorial extensions
If this is right
- The univariate LO theorem of [BHKS24] becomes a special case of Theorem 5.2 by taking the Y-degree parameter to be 1, so every code known to be list-decodable through LO codes automatically satisfies the new sufficient condition.
- Permuted product codes of [BST24] are shown to be B-LELO codes, so their list-decodability up to 1-R-O(epsilon) with list size q^{O(1/epsilon^5)} follows directly from Theorem 5.2.
- Folded Reed-Solomon, multiplicity, and affine folded Reed-Solomon codes, already known as LELO codes, are all instances of B-LO codes and therefore also satisfy the unified criterion.
- Whenever the four hypotheses of Theorem 5.2 hold, decoding reduces to solving two linear systems, one for interpolation and one triangular recovery system, so the list of candidate messages can be found in polynomial time in the block length.
Reading between the lines
- The proof of Theorem 5.2 relies on Observation 3.3, which is fully justified only if the matrices Mx and My commute on the image of L; all examples in the paper use diagonal, hence commuting, matrices, so the missing commutativity hypothesis may be hidden in the statement. A clean fix would be to add an explicit commutativity or joint-normal-family condition to Definition 3.2.
- Because B-LELO codes need not be maximum-distance separable, Theorem 5.2 does not tie the list-decoding distance D to the rate alone. This suggests searching for new capacity-achieving codes by choosing non-diagonal commuting matrices Mx,My that give better distance or smaller list size than the diagonal constructions.
- The interpolation argument is degree-based rather than ideal-based, so the same proof should extend to messages in more than two variables; the paper notes this possibility without developing it. A testable extension is to state and prove the analogous theorem for F[X1,...,Xm] and check whether higher-dimensional permuted product codes satisfy the corresponding list-composition condition.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes bivariate linear operator (B-LO) codes, a two-variable generalization of the linear operator (LO) code framework of BHKS24. A B-LO code evaluates a bivariate message polynomial p(X,Y) under a family of linear operators L_0,...,L_{s-1} at a set of points A, and a B-LELO code is one whose family satisfies L(Xp)=M_x L(p) and L(Yp)=M_y L(p). The authors show that LO codes embed into B-LO codes, that permuted product codes (PPCs) of BST24 are B-LELO codes, and state a sufficient condition (Theorem 5.2) for a B-LELO code to be list-decodable up to a distance D. The proof follows the BHKS24 interpolation-plus-lower-triangular-system strategy. They then apply the criterion to reprove capacity-achieving list-decodability of PPCs and to recover the univariate LO list-decodability theorem as a special case.
Significance. If the main theorem is correct, the paper makes a solid conceptual contribution: it extends the LO-code abstraction to bivariate messages, thereby capturing permuted product codes within the same ideal-theoretic/list-decoding framework as folded Reed-Solomon, multiplicity, and affine folded Reed-Solomon codes. The application to PPCs gives a unified derivation of a known capacity-achieving result rather than a new construction, but the unification is itself valuable. The paper is honest about a limitation of the bivariate setting (F[X,Y] is not a PID, so B-LELO codes need not be MDS, and the distance D must be supplied as a hypothesis). The proof is presented as a linear-algebraic interpolation argument with no fitted parameters, and all applications are explicit. However, as discussed below, the main theorem's proof has a load-bearing well-definedness gap in the use of matrix polynomials, and the distance parameter D is used inconsistently across statement and proof; these issues are repairable but require revision.
major comments (3)
- [Definition 3.2, Observation 3.3, and Section 6.1, Eq. (6.2)] The identity L(q(X,Y)p(X,Y)) = q(M_x(X,Y),M_y(X,Y))L(p(X,Y)) in Observation 3.3 is not justified by Definition 3.2 as stated. Definition 3.2 only gives L(Xp)=M_x L(p) and L(Yp)=M_y L(p). Commutativity of M_x and M_y on Im(L) does follow from XY=YX: (M_xM_y-M_yM_x)L(p)=L(XYp)-L(YXp)=0, but the paper neither states nor proves this. This gap becomes load-bearing in the interpolation step of Theorem 5.2: Eq. (6.2) defines constraints using Q_i(M_x,M_y)(x,y) applied to the vectors h_{G_i,(x,y)} c_{(x,y)}, which for an arbitrary received word c need not lie in Im(T). The later use in Eq. (6.9) applies the same matrix polynomial to T(G_i(p))(x,y), which does lie in Im(T), where a canonical action exists. Thus Q_i(M_x,M_y)(x,y) is not well-defined as a matrix acting on all of F^r without an explicit convention (for example, fixing a monomial order for evaluating noncommuting matrix polynomials, or an explicit commutativity/extension assumption). Since this interpolation equation is the foundation of the entire proof, the theorem is not proven in its stated generality, even though all concrete examples have diagonal, hence commuting, matrices.
- [Theorem 5.2 and Section 6.2] The distance parameter D is used inconsistently between relative and absolute form. In Definition 2.1 and in the applications (e.g., Section 7 uses D=1-r/(w(r-t+1))-k/n), D is a relative distance. But the proof in Section 6.2 says 'if the number of non-zero evaluations ... is less than D, we must have R_p ≡ 0' and 'if there are less than D errors', which treats D as an absolute count. The correct comparison should be against Dn when D is relative. A similar inconsistency appears in item 4: Theorem 5.2 states Diag(G) has distance tk-ell (absolute), while Theorem 1.3 states the analogous condition as relative distance 1-ell/(tk). The intended meaning is recoverable, but the main theorem and its proof should state all distances in the same normalization, or explicitly define D as the absolute minimum distance.
- [Section 7, parameter choices for Diag(G)] The application to PPCs assumes that Diag(G) is formed by stacking t generator matrices of RS[w,k] and therefore has distance (k-w+1)t. This is only positive when k>w (or at least k>=w). The text fixes R and epsilon and chooses s, w, and t, but does not state that n and k=Rsn/t must be chosen large enough so that k>w. Without such a condition, the proposed G need not satisfy hypothesis 4 of Theorem 5.2. This is a parameter-regime gap in the capacity-achieving claim; it can be fixed by explicitly requiring n to be sufficiently large, but as written the application is incomplete.
minor comments (6)
- [Definition 2.5] The set notation for the Reed-Solomon code contains a typo: '(F_q)<k[X]' should be 'F_q[X]<k'.
- [Definition 2.7 and Section 4.2] The index ranges in the Permuted Product code definition and in Eq. (4.2) are written as 'n_{i=0}'; they should be 'n-1_{i=0}'.
- [Section 4.2, Eq. (4.2)] The displayed encoding uses 'L(p)(a_i)' without defining a_i; the intended notation is the evaluation set A, whose elements are (x,y) pairs.
- [Observation 5.4] The proof writes B-LELO^{A'}_{k+nr/w,1}(T') instead of B-LELO^{A'}_{d1,d2}(T') with d1=k+floor(nr/w), which makes the floor invisible; please make the notation match the stated d1.
- [Section 7] The relative distance is printed as 'D=1-r/w(t-t+1)-k/n'; the denominator should be w(r-t+1). Also, 'ell_2(X)=gamma X' should presumably be 'ell_2(Y)=gamma Y'.
- [Section 6.2] There is a typo: 'non-zero elemenets' should be 'non-zero elements'.
Circularity Check
No significant circularity: Theorem 5.2 is proved from the B-LO definitions via interpolation, degree counting, and a lower-triangular coefficient system; the LO-code theorem is derived as a special case; and the PPC list-decodability result is a new derivation through Theorem 5.2 rather than an import of [BST24]'s theorem. No self-citations occur.
full rationale
None of the seven circularity patterns is present. Theorem 5.2 is a genuine implication proved from the definitions in Section 6: the interpolation system (Eq. 6.2) has more variables than constraints (Eq. 6.3); agreement positions force T(R_p)(x,y)=0; the input distance D of B-LELO_{d1,d2}(T) is used exactly as a stated hypothesis; and the q^ell list-size bound follows from the stated distance tk-ell of Diag(G) via the lower-triangular system whose diagonal entries are u x Diag(G) (Eq. 6.14). The radius D and the list-size exponent ell are not fit from the conclusion; they are hypotheses used in the proof. Section 7 computes both the B-LELO(T) distance (from row-wise RS distances: each nonzero row has at least n-d2 nonzero entries) and the Diag(G) distance (Diag(G)i,ak+b = gamma^{ib}, giving stacked RS generator matrices), then applies Theorem 5.2; the asymptotic bound 1 - R - O(eps) with list size q^{1/eps^5} is honest arithmetic, so the PPC result is a re-derivation of the known [BST24] theorem, not a re-import of its list-decoding statement. Theorem 1.2 (PPC is a B-LELO code) is a code-equivalence proof from the definitions, not a definition that presupposes list-decodability. The paper cites [BHKS24] and [BST24] as prior work, but neither is authored by Putterman or Zaripov, so there is no self-citation, and no uniqueness theorem or ansatz is imported from the present authors' own prior work. The one flagged issue is a rigor/presentation gap, not circularity: Observation 3.3 claims L(qp)=q(Mx,My)L(p), and Eqs. (6.2)/(6.7) evaluate the matrix polynomial Q_i(Mx,My) without stating a monomial-order convention, since Mx and My are not asserted to commute as matrices. This is repairable: from L(XYp)=L(YXp) one obtains Mx My = My Mx on Im(L), which makes the identity valid on every vector to which the proof applies it, provided a fixed product order (Mx before My) is adopted. That concern belongs in the correctness pass, not the circularity pass. Overall the derivation chain is self-contained; each headline result is a derived consequence of the framework's definitions, not an equivalent restatement of its own inputs.
Assumptions & free parameters
assumptions (4)
- standard math F[X,Y] is not a principal ideal domain, so ideals I_{(x,y)}(L) need not be principal.
- domain assumption Rows of B-LELO^A_{d1,d2}(T) in the PPC application are Reed-Solomon codewords because evaluation points have distinct y-coordinates within each row.
- standard math A nonzero univariate polynomial of degree less than w has at most w-1 roots, giving the RS-code distance of Diag(G).
- ad hoc to paper Mx and My commute on the image of L whenever Observation 3.3 is applied.
Cite this review
Pith. "Pith review of Bivariate Linear Operator Codes." pith.science (2026). https://pith.science/paper/LPIJDKWX
@misc{pith2026241116596,
author = {Pith},
title = {Pith review of: Bivariate Linear Operator Codes},
year = {2026},
howpublished = {\url{https://pith.science/paper/LPIJDKWX}},
note = {Machine review of arXiv:2411.16596}
}
read the original abstract
In this work, we present a generalization of the linear operator family of codes that captures more codes that achieve list decoding capacity. Linear operator (LO) codes were introduced by Bhandari, Harsha, Kumar, and Sudan [BHKS24] as a way to capture capacity-achieving codes. In their framework, a code is specified by a collection of linear operators that are applied to a message polynomial and then evaluated at a specified set of evaluation points. We generalize this idea in a way that can be applied to bivariate message polynomials, getting what we call bivariate linear operator (B-LO) codes. We show that bivariate linear operator codes capture more capacity-achieving codes, including permuted product codes introduced by Berman, Shany, and Tamo [BST24]. These codes work with bivariate message polynomials, which is why our generalization is necessary to capture them as a part of the linear operator framework. Similarly to the initial paper on linear operator codes, we present sufficient conditions for a bivariate linear operator code to be list decodable. Using this characterization, we are able to derive the theorem characterizing list-decodability of LO codes as a specific case of our theorem for B-LO codes. We also apply this theorem to show that permuted product codes are list decodable up to capacity, thereby unifying this result with those of known list-decodable LO codes, including Folded Reed-Solomon, Multiplicity, and Affine Folded Reed-Solomon codes.
Reference graph
Works this paper leans on
-
[1]
Ideal-theoretic explanation of capacity-achieving decoding
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan. Ideal-theoretic explanation of capacity-achieving decoding. IEEE Trans. Inf. Theory , 70(2):1107--1123, 2024
work page 2024
-
[2]
Explicit subcodes of reed-solomon codes that efficiently achieve list decoding capacity
Amit Berman, Yaron Shany, and Itzhak Tamo. Explicit subcodes of reed-solomon codes that efficiently achieve list decoding capacity. CoRR , abs/2401.15034, 2024
arXiv 2024
-
[3]
List decoding for noisy channels
Peter Elias. List decoding for noisy channels. In Wescon Convention Record, Part 2 . Institute of Radio Engineers, 1957
work page 1957
-
[4]
Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. CoRR , abs/cs/0511072, 2005
work page Pith review arXiv 2005
-
[5]
Linear-algebraic list decoding for variants of reed-solomon codes
Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of reed-solomon codes. Electron. Colloquium Comput. Complex. , TR12-073 , 2012
work page 2012
-
[6]
Improved list decoding of folded reed-solomon and multiplicity codes
Swastik Kopparty, Noga Ron - Zewi, Shubhangi Saraf, and Mary Wootters. Improved list decoding of folded reed-solomon and multiplicity codes. SIAM J. Comput. , 52(3):794--840, 2023
work page 2023
-
[7]
Itzhak Tamo. Tighter list-size bounds for list-decoding and recovery of folded reed-solomon and multiplicity codes. CoRR , abs/2312.17097, 2023
arXiv 2023
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.