{"id":"b1efbe02-4bf4-430e-bbf1-2c67fc9e92bc","arxiv_id":"2411.16596","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Bivariate linear operator codes generalize linear operator codes and prove a unified list-decodability condition that captures permuted product codes.","lead":"Error-correcting codes help messages survive noise. This paper widens an algebraic framework so a broader family of such codes, including permuted product codes, can be shown to reach the theoretical limits of list decoding.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.2's proof evaluates q(Mx,My) without defining matrix polynomial evaluation; Mx,My commute on Im(T) but not necessarily globally, so the interpolation step (Eq. 6.2) is not well-defined as written. The gap is repairable but requires an explicit commutativity or fixed-ordering assumption.","rationale":"The reader correctly identifies the commutativity issue as the weakest point in the proof of Theorem 5.2. I agree that the proof uses the identity L(qp)=q(Mx,My)L(p) in a way that requires care, and that the paper neither states nor proves the needed commutativity. However, the reader's formulation slightly overstates the problem: Mx and My do commute on Im(L) as an immediate consequence of Definition 3.2 (because L(XYp)=L(YXp)), so the identity itself is true on the image. The real gap is in the interpolation step, where q(Mx,My) is evaluated on arbitrary vectors outside Im(T), making the expression undefined without an explicit ordering or a global commuting choice. This is repairable without changing the theorem's statement, but a rigorous version of the paper must include such a clarification. Additionally, the proof of Section 6.2 conflates relative distance D with absolute Hamming distance ('less than D' should be 'less than nD'), a minor but real notational issue that should be fixed. Since the central construction and all examples are correct, the proper verdict is CONDITIONAL: the paper should be accepted once these proof clarifications are added.","tokens_in":86,"tokens_out":28177,"duration_ms":382428,"concrete_test":"Formally re-derive Observation 3.3: (1) prove (MxMy−MyMx)T(p)=0 for all p from Definition 3.2, establishing commutation on Im(T); (2) then check whether, for a fixed monomial order (e.g., all Mx before My), the interpolation system (Eq. 6.2) yields a nonzero Q and whether Eq. 6.7 remains valid when Mx,My do not commute globally. If both hold, amend the paper with a remark on the implicit ordering/commutation and keep Theorem 5.2 unchanged; if a counterexample shows the interpolation constraints depend on the order in a way that breaks the 'close enough codewords' step, then Theorem 5.2 must be restricted to families whose Mx,My commute globally.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central proof step is Observation 3.3, which claims that for a linearly-extendible family L with matrices Mx,My, one has L(q·p) = q(Mx,My)·L(p). As written, q(Mx,My) is ambiguous because Mx and My are matrices that are not asserted to commute. Definition 3.2 only gives L(Xp)=Mx·L(p) and L(Yp)=My·L(p). However, since X and Y commute, L(XYp)=L(YXp), which yields (MxMy−MyMx)L(p)=0 for all p; hence Mx and My commute on the subspace Im(L). This is enough to make the identity true on Im(L), but the paper neither states nor proves it. The problem becomes load-bearing in Section 6.1: the interpolation constraints (Eq. 6.2) apply Qi(Mx,My) to vectors h_{Gi,(x,y)}·c_{(x,y)}, which are arbitrary vectors in F^r and need not lie in Im(T). Thus Qi(Mx,My) must be well-defined as a matrix for all vectors, not just on Im(T). One can repair this by fixing a monomial order for evaluating Qi(Mx,My), or by choosing commuting representatives for Mx,My (e.g., zeroing out a complement of Im(T)), but the proof as written leaves the expression undefined. This is a genuine rigor gap in the theorem's stated generality, even though all concrete examples in the paper use diagonal, hence commuting, matrices.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":97,"tokens_out":13350,"duration_ms":225508,"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":[{"comment":"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.","section":"Definition 3.2, Observation 3.3, and Section 6.1, Eq. (6.2)"},{"comment":"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":"Theorem 5.2 and Section 6.2"},{"comment":"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.","section":"Section 7, parameter choices for Diag(G)"}],"minor_comments":[{"comment":"The set notation for the Reed-Solomon code contains a typo: '(F_q)<k[X]' should be 'F_q[X]<k'.","section":"Definition 2.5"},{"comment":"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":"Definition 2.7 and Section 4.2"},{"comment":"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.","section":"Section 4.2, Eq. (4.2)"},{"comment":"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":"Observation 5.4"},{"comment":"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":"Section 7"},{"comment":"There is a typo: 'non-zero elemenets' should be 'non-zero elements'.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is clearly written and the proposed framework is a reasonable and useful generalization. The main obstacle is the well-definedness gap around q(M_x,M_y) in the proof of Theorem 5.2; this is local and repairable, but it is load-bearing for the stated theorem, so I do not think a minor revision is appropriate. The distance-normalization inconsistency and the Section 7 parameter condition should be fixed in the same revision. I recommend major revision rather than rejection because the central idea is sound and all known examples avoid the noncommutativity issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real generalization, not a repackaging. The bivariate extension of linear operator codes is the right minimal move to capture permuted product codes, and Theorem 5.2 is a genuine unifying sufficient condition: it gives the LO list-decoding theorem as a special case and yields PPC list-decodability as a corollary. The paper is worth a serious referee.\n\nWhat it does well: the reduction from PPCs to B-LELO (Section 4.2) is clean and correct; the diagonal generator-matrix condition is a natural bivariate analogue of the BHKS24 condition; and the interpolation proof is a careful adaptation of the Guruswami-Wang linear-algebraic method. The paper is clearly written and self-contained. The observation that univariate LO codes cannot express bivariate message polynomials, so the extension is necessary, is correct.\n\nThe soft spot is real and load-bearing but repairable. Observation 3.3 asserts L(q(X,Y)p) = q(Mx,My)L(p) for any q. That identity requires Mx and My to commute on the image of L. From Definition 3.2 alone you only get L(Xp)=Mx L(p) and L(Yp)=My L(p). Since X and Y commute, L(XYp)=L(YXp), so MxMy and MyMx agree on Im(L). That is enough to make the identity true on Im(L), but the paper does not state or prove it. Worse, the interpolation constraints in Eq. (6.2) evaluate Qi(Mx,My) on vectors h_{Gi,(x,y)} c_{(x,y)}, which are arbitrary vectors in F^r and need not lie in Im(T). So as written, q(Mx,My) is not well-defined as a matrix on all of F^r. This is not a fatal flaw: all examples in the paper have diagonal Mx and My, which commute globally, and the gap can be closed either by assuming commutativity or by choosing a fixed monomial order for the matrix polynomial. But it must be fixed before the theorem is stated in full generality.\n\nMinor point: the paper uses D both as the distance of the T-code and as the list-decoding radius in Theorem 5.2; it would help to separate the two. The PPC application itself is a new derivation of a known result, but the unification is the contribution, and the authors are transparent about that.\n\nFor whom: coding theorists working on list decoding and algebraic code families. It deserves a serious referee with the expectation of minor revision. I would engage with it.","headline":"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.","tokens_in":17095,"tokens_out":2099,"would_cite":true,"duration_ms":19637,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B05","11T71","68P30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["bivariate linear operator codes","list decoding capacity","linearly-extendible linear operators","permuted product codes","folded Reed-Solomon codes","multiplicity codes","interpolation decoding","triangular linear systems"],"falsifier":"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.","tokens_in":16042,"feed_emoji":"📡","tokens_out":8203,"duration_ms":75158,"temperature":0.7,"pith_summary":"The paper claims that many capacity-achieving list-decodable codes are instances of one broader family, which it calls bivariate linear operator (B-LO) codes. These encode a bivariate message polynomial by applying a tuple of linear operators and evaluating at a set of points, generalizing the earlier linear operator (LO) code framework from univariate to bivariate messages. The central result is a sufficient condition, Theorem 5.2, under which a B-LO code is list-decodable up to a specified distance with list size q to the ell. If the condition holds, the theorem covers folded Reed-Solomon, multiplicity, affine folded Reed-Solomon, and permuted product codes, giving a unified explanation of their list-decodability.","feed_headline":"Bivariate operator codes unify capacity-achieving list-decoding proofs.","feed_subtitle":"A single sufficient condition covers permuted product, folded Reed-Solomon, and multiplicity codes.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines LO and LELO codes and Theorem 2.12, the univariate list-decodability criterion that this paper generalizes; supplies the proof structure.","marker":"[BHKS24]"},{"why":"Introduces permuted product codes with bivariate messages, the family that Theorem 1.2 embeds into B-LELO and whose list-decodability Theorem 5.2 recovers.","marker":"[BST24]"},{"why":"Provides the linear-algebraic list-decoding strategy for folded Reed-Solomon variants that the interpolation and triangular-solving proof of Section 6 generalizes.","marker":"[GW12]"},{"why":"Defines folded Reed-Solomon codes, the prototypical bundled capacity-achieving family that is shown to be an instance of LO and hence of B-LO codes.","marker":"[GR05]"}],"fun_headline_variants":["Bivariate operator codes unify list-decoding proofs for more families","New bivariate framework captures permuted product codes","Generalized operator codes: one theorem, many capacity-achieving codes","Bivariate linear operators extend list-decodable code universe"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bivariate operator codes unify list-decoding proofs for more families","New bivariate framework captures permuted product codes","Generalized operator codes: one theorem, many capacity-achieving codes","Bivariate linear operators extend list-decodable code universe"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1637,"prompt_tokens":1191,"completion_tokens":446,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":807,"completion_tokens_details":{"reasoning_tokens":376}},"tokens_in":807,"tokens_out":446,"duration_ms":5151,"temperature":1.0,"reasoning_tokens":376,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:58:29.392896+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}