Skip to content
DraconiticResearch
Search Sources API
182,469 studies31 sourcesUpdated 24 min ago
PreprintCC BY 4.0arXiv

Symmetric Models for Syndrome Decoding

  • Elisa Gorla
  • Simone Trebiani
Open at sourcePDFDOICite

Abstract

This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our approach to solve other variants of the SDP.

Related

  1. A $π/ 4$ lower bound for random access in symmetric linear ensembles under optimal decoding
    Daniella Bar-Lev, Ohad Elishco, Ryan Gabrys
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  2. HARS: LDPC Bit-Flipping Decoding With Initial-Syndrome-Conditioned Parameter Mapping and Local-Reliability Weighting
    Tung Hsu Wu, Huang-Chang Lee
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Hamming Ideals and Grobner Bases for ISD-like Syndrome Decoding
    Roberto La Scala, Marco Marchesin, Sharwan K. Tiwari
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
  4. Temporal Degeneracy Limits Message Passing Decoding of QLDPC Codes Under Repeated Noisy Syndrome Measurements
    Dimitris Chytas, Nithin Raveendran, Bane Vasić
    arXivPreprintarXiv licenceFull textGeneral mathematicsQuantum physics & quantum informationarXiv
  5. Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
    Joshua Brakensiek, Yeyuan Chen, Aaron Putterman +2
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{gorla2026symmetric,
  title = {{Symmetric Models for Syndrome Decoding}},
  author = {Elisa Gorla and Simone Trebiani},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.14052},
  eprint = {2609.14052},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14052},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Symmetric Models for Syndrome Decoding
AU  - Elisa Gorla
AU  - Simone Trebiani
PY  - 2026
DA  - 2026/09/12
PB  - arXiv
DO  - 10.48550/arxiv.2609.14052
UR  - https://arxiv.org/abs/2609.14052
AB  - This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our approach to solve other variants of the SDP.
ER  -