Decoding Algorithms for Tensor Codes

1. Problem Statement

The paper addresses the decoding of Tensor Codes, a generalization of matrix-based rank-metric codes (specifically Delsarte-Gabidulin-Roth codes) to higher-order tensors.

• Context: Tensor codes are subspaces of order-$r$ tensors (specifically order-3 in the main body, generalized to order-$m+1$) endowed with the tensor-rank metric. The tensor-rank of a tensor is the minimum number of rank-1 tensors required to sum to it.
• Challenge: While decoding algorithms exist for low tensor-rank errors (e.g., Roth's algorithms for rank 1 and 2), they often suffer from exponential complexity in the decoding radius or are limited to specific code constructions.
• Goal: The authors aim to develop polynomial-time decoding algorithms for a generalized class of tensor codes that can correct a broader range of errors (beyond just low tensor-rank) by leveraging the internal structure of the codes as subcodes of direct sums of Gabidulin codes and utilizing algebraic properties of bilinearized polynomials.

2. Methodology and Theoretical Framework

The authors build their approach on several key theoretical pillars:

A. Generalized Tensor Codes

They define a class of Roth-tensor codes $C_\alpha(S)$ as evaluation codes of bilinearized $q$-polynomials (and multilinearized for higher orders).

• Polynomial Representation: Codewords are evaluations of polynomials $f(X, Y) = \sum f_{i,j} X^{q^i} Y^{q^j}$ over a basis $\alpha$ of $\mathbb{F}_{q^n}$.
• Structure: These codes are subspaces of $\mathbb{F}_{q^n}^{n \times n}$. Crucially, every row and every column of a codeword in $C_\alpha(S)$ is itself a codeword in a Gabidulin code (a Maximum Rank Distance code).
• Metrics: The paper introduces and analyzes several metrics that serve as lower bounds for the tensor-rank:
  • Fibre-weight ($w_{fs}$): The dimension of the $\mathbb{F}_q$-span of the entries (equivalent to the rank of the flattened matrix).
  • Slice-space weight ($w_{ss}$): The dimension of the space spanned by the slices (rows or columns) of the tensor.
  • Tensor-rank ($trank$): The standard metric.
  • Key Insight: $w_{fs}(T) \leq trank(T)$ and $w_{ss}(T) \leq trank(T)$. Decoding with respect to these weaker metrics implies decoding with respect to the tensor-rank metric.

B. Decoding Strategies

The paper proposes four main algorithms (and their generalizations) divided into two categories:

1. Fibre-wise Decoding (Algorithms 1, 1', 2)

• Concept: Exploits the fact that rows and columns of the tensor are Gabidulin codewords.
• Algorithm 1/1': Decodes columns (or rows) independently using a standard Gabidulin decoder. This corrects errors where every column (or row) has a rank below the Gabidulin decoding radius.
• Algorithm 2 (Two-way): A sequential approach. First, decode columns to get an intermediate word; then decode the rows of this intermediate word.
• Capability: This approach corrects errors that do not necessarily have low tensor-rank but satisfy specific constraints on the rank distribution of their rows/columns. It effectively corrects errors where a large subset of rows/columns are low-rank, even if others are high-rank.

2. Radical Decoding (Algorithms 3, 4)

• Concept: A generalization of the Loidreau-Overbeck decoding method for Gabidulin codes, adapted for tensor codes using a "left-Euclidean" division on bilinearized polynomials.
• Mechanism:
  1. Formulate a linear system to find a non-zero pair $(V(Z), N(X, Y))$ such that $V(R) = N(\alpha)$, where $R$ is the received word.
  2. $V(Z)$ is a linearized polynomial that vanishes on the error entries.
  3. Factorize $N(X, Y)$ as $V(f(X, Y))$ to recover the message polynomial $f$.
• Capability: This method corrects errors based on the sum of the fibre-weight and the minimum slice-space weight ($w_{fs} + \min(w_{ss})$). It can correct errors with a fibre-weight up to roughly $n - \mu - 1$, which is nearly double the radius of standard Gabidulin decoding.

3. Interleaving and Supercode Techniques

• The paper discusses applying interleaved decoding (treating the tensor as a stack of Gabidulin codes) and supercode decoding.
• These techniques allow for probabilistic correction of errors with even higher weights (up to $\approx \frac{2n}{2n+1}(n-\mu-1)$) with a low failure probability.

3. Key Contributions

1. Generalized Code Construction: Defined a broad family of tensor codes based on arbitrary support sets $S$ of polynomial exponents, generalizing Roth's original construction.
2. Polynomial Complexity Decoders: Introduced decoding algorithms (Fibre-wise and Radical) that run in polynomial time with respect to the tensor size ($n$) for any fixed decoding radius, unlike previous generalizations of Roth's rank-2 decoder which were exponential in the radius.
3. Extended Decoding Radius: Demonstrated that these algorithms can correct errors with tensor-rank higher than the standard bound ($\lfloor (d-1)/2 \rfloor$). Specifically, they correct errors where the "slice" or "fibre" structure is sparse, even if the global tensor rank is high.
4. Metric Hierarchy: Established rigorous bounds showing that decoding with respect to fibre/slice weights implies decoding for the tensor-rank metric, providing a new perspective on error correction capabilities.
5. Higher-Order Generalization: Successfully extended all definitions, metrics, and algorithms from order-3 tensors to order-$(m+1)$ tensors.

4. Results and Performance Analysis

• Error Correction Capability:
  • Algorithm 2 corrects a strictly larger set of errors than Algorithm 1. For example, it can correct errors where most columns are low-rank, even if a few are high-rank (provided the high-rank columns are sparse).
  • Algorithm 4 (Radical) corrects errors where $w_{fs}(E) + \min(w_{ss}(E)) \leq n - \mu - 1$. This allows correcting errors with tensor-rank significantly larger than the unique decoding radius of the code.
  • Asymptotic Bounds: The paper provides lower bounds on the number of correctable errors. For large $n$, the number of correctable errors by the proposed algorithms grows significantly faster (exponentially in $n^2$) compared to the number of low tensor-rank errors (which grows linearly in $n$).
• Complexity:
  • Fibre-wise (Alg 1 & 2): $O(n^4 \log n)$ or $O(n^5)$ operations over $\mathbb{F}_q$.
  • Radical (Alg 3 & 4): Solves a linear system of size $n^2 \times |S+t|$. The complexity is $O(n^9)$ in the worst case (for order-3), but generally polynomial.
  • Generalized Order $m$: Complexity scales as $O(n^{m+2} \log n)$ for fibre-wise and $O(n^{3(m+1)})$ for radical decoding.
• Comparison with Roth: While Roth's original codes for specific parameters ($C(n, 3, 3; q)$) have higher dimension, the proposed generalized codes with the new decoders offer a better trade-off between dimension and the volume of correctable errors in the tensor-rank metric.

5. Significance

• Network Coding & Cryptography: Tensor codes are vital for network coding (handling burst errors) and rank-metric cryptography (post-quantum security). Efficient decoding is the bottleneck for practical implementation.
• Breaking the Exponential Barrier: By achieving polynomial complexity for decoding radii that were previously only accessible via exponential algorithms, this work makes high-rank tensor codes practically viable.
• New Decoding Paradigm: The shift from viewing errors purely by their tensor-rank to analyzing their slice and fibre structures opens new avenues for decoding. It shows that "structured" high-rank errors (e.g., errors concentrated in specific rows/columns) are easier to correct than random high-rank errors.
• Open Source: The authors provide a MAGMA implementation, facilitating further research and verification of these complex algebraic decoding techniques.

In summary, this paper provides a comprehensive framework for decoding generalized tensor codes, moving beyond the limitations of previous low-rank decoders to offer polynomial-time solutions for a significantly wider class of errors, leveraging the rich algebraic structure of Gabidulin codes embedded within the tensor space.