Efficient Polynomial-Time Decoding of Simplicial Anticodes with Near-Optimal Performance
Abstract
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.
Related
- Distributed LLM Inference via Communication-Efficient Speculative Decoding
- Efficient Perturbation-Based SC Decoding for Long Polar Codes
- Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding
- Chase-like Decoding: Test-Pattern Design and Performance Analysis
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
BibTeX
@misc{loritelopez2026efficient,
title = {{Efficient Polynomial-Time Decoding of Simplicial Anticodes with Near-Optimal Performance}},
author = {Antonio Jesús Lorite-López and Daniel Camazón-Portela and Juan Antonio López-Ramos},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29631},
eprint = {2608.29631},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29631},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Efficient Polynomial-Time Decoding of Simplicial Anticodes with Near-Optimal Performance
AU - Antonio Jesús Lorite-López
AU - Daniel Camazón-Portela
AU - Juan Antonio López-Ramos
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29631
UR - https://arxiv.org/abs/2608.29631
AB - 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.
ER -