Source-linked AI summary
Efficient Polynomial-Time Decoding of Simplicial Anticodes with Near-Optimal Performance
Antonio Jesús Lorite-López, Daniel Camazón-Portela, Juan Antonio López-Ramos
TL;DR
Simplicial-complex codes lacked an efficient decoding method, motivating an approach that exploits complementary-complex structure. The proposed algorithm gives an explicit correction bound, is asymptotically optimal under bounded maximal-face dimension, and reaches theoretical capability for specific families.
Problem
Simplicial-complex codes had no previously known efficient decoding method, despite their structural and cryptographic relevance.
Method
The paper exploits complementary simplicial anticodes to construct an efficient decoder that recovers messages directly.
Results
The correction-capability ratio converges to 1 as code length increases under natural assumptions, and specific anticode families achieve theoretical capability.
Takeaways & Limitations
The algorithm provides a computable near-optimal decoder for simplicial anticodes and is exactly optimal for identified families.
Takeaways & Limitations
The algorithm does not always attain the maximum theoretical error-correction capability, and its asymptotic guarantee assumes bounded maximal-face dimension.
Abstract
from arXiv · showhide
In this work, we propose an efficient decoding algorithm for codes arising from simplicial complexes, a family of binary linear codes for which no decoding method of this type was previously known. Although the algorithm does not always attain the maximum theoretical error-correcting capability, it provides an explicit bound that can be computed directly from the structure of the complex. Moreover, this bound is asymptotically optimal: the ratio between the guaranteed correcting capability and the theoretical maximum converges to $1$ as the code length increases, under natural assumptions on the dimension of the maximal faces. The correction capability is also presented in specific examples. Finally, we introduce specific families of simplicial complexes where the algorithm successfully reaches this theoretical bound.
1 Introduction
Simplicial-complex codes have useful structure but lacked an efficient decoding algorithm. This paper exploits complementary complexes to decode directly, with near-optimal correction guarantees and exact optimality for specific families.
- No efficient decoding algorithm was previously available for simplicial-complex codes, limiting applications including cryptographic contexts.
- The paper exploits complementary simplicial complexes to construct an efficient decoding algorithm.Their complementary-set structure provides a compact representation of the associated codes.
- The procedure recovers the original message directly, avoiding an additional linear-system-solving step after decoding.
- The algorithm provides an explicit, easily computable correction bound, although it does not always attain the maximum theoretical capability.
- The ratio between guaranteed and theoretical correction capabilities converges to 1 as code length increases under natural assumptions, making the algorithm asymptotically optimal.
- For simplex, first-order Reed-Muller, and MacDonald codes over F2, viewing the codes as anticodes yields maximum correction capability.
2 Preliminaries
The preliminaries define simplicial complexes, their complements, and the associated binary anticodes. They also summarize structural and distance properties relevant to decoding and optimality.
- A simplicial complex over [m] is a family of subsets closed under taking subsets and can be described by its maximal faces.
- The complement of a simplicial complex is characterized by its minimal faces.
- The anticode associated with the complementary complex is generated by its incidence matrix, whose transposed columns are characteristic vectors of complementary faces.
- The associated code can equivalently be defined using characteristic vectors of faces of the original simplicial complex.
- The parameters, especially minimum distance, are generally unknown, although some families admit explicit determination.
- For a nonempty subset σ of [m], exactly 2^(m-1) subsets contain an odd number of elements of σ.
- Under stated conditions on maximal faces, the maximum codeword weight is attained by selecting one vertex exclusively from each maximal face, yielding explicit anticode parameters.
- Necessary and sufficient optimality conditions for these anticodes have also been established.
3 Main results
The paper develops a polynomial-time simplicial decoding algorithm that estimates information bits from paired or individually usable generator-matrix columns, then improves the final bit through majority voting. It provides an explicit error-correction bound, approaches theoretical capability asymptotically under bounded maximal-face dimension, and achieves the theoretical capability for several complex families.
- Decoding algorithm: The decoder recovers information bits by pairing generator-matrix columns that differ in one coordinate and using their received-bit sums as estimates.It aggregates multiple estimates by majority vote; the final unrecovered bit can use independent estimates from columns containing that coordinate.
- Computational complexity: O((k −1)n log n) is the overall running time, making the decoding algorithm polynomial in the code length.The algorithm avoids pre-computation and the construction of PD-sets required by previous approaches.
- Error-correction capability: The algorithm provides an explicit, easily calculable upper bound on correctable errors from the simplicial complex structure.Its guaranteed capability is characterized using the links or subcomplexes associated with selected coordinates.
- Asymptotic performance: As the code length tends to infinity, the guaranteed capability converges to the theoretical correction capability when the dimension of maximal sets remains bounded.The simulated average ratio between practical and theoretical capability also converges toward 1 as the number of vertices increases.
Declarations
The authors report equal contributions across conceptualization, methodology, investigation, analysis, and manuscript preparation, alongside funding, data-availability, and conflict-of-interest disclosures.
- The listed contributions include conceptualization, methodology, investigation, analysis, and writing and editing of the manuscript.
- All authors contributed equally and approved the final manuscript for publication.
- The research was supported by grants PID 2022-140934OB-I00, FQM-425, and PID2022-138906NB-C21, including ERDF funding.
- The authors declare no conflicts of interest, and code used to generate Figure 1 is available from the corresponding author upon request.