Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 40 min ago
PreprintarXiv licencearXiv

Block basis reduction for linear codes in non-Hamming metrics

  • N. S. Kolesnikov
  • S. A. Novoselov
Open at sourcePDFDOICite

Abstract

In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~π’ͺ(n4 q3) operations in~𝔽q, where~n is the length of the code and~q is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.

Related

  1. Block diagonal preconditioners for arrow-shaped multiple saddle-point linear systems
    Luca Bergamaschi, Michele Bergamaschi
    arXivPreprintCC BY-SA 4.0Full textNumerical analysis & scientific computingarXiv
  2. A variant of the block preconditioner for indefinite complex symmetric linear systems
    Mehdi Makhdomi, Davod Khojasteh Salkuyeh
    arXivPreprintCC0Full textNumerical analysis & scientific computingarXiv
  3. Block numerical ranges for linear relations
    Rabeb Aydi, Hannes Gernandt, Omaima Kchaou +2
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  4. Randomized Symplectic Model Reduction: One-Pass Basis Construction and Sketched Hamiltonian Assembly
    Robin Herkert, Bernard Haasdonk, JΓΆrg Fehr
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
  5. Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs
    Irina Podlipnova, Maxim Mashtaler, Artem Agafonov +2
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{kolesnikov2026block,
  title = {{Block basis reduction for linear codes in non-Hamming metrics}},
  author = {N. S. Kolesnikov and S. A. Novoselov},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.26808},
  eprint = {2610.26808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.26808},
}
RIS
TY  - UNPB
TI  - Block basis reduction for linear codes in non-Hamming metrics
AU  - N. S. Kolesnikov
AU  - S. A. Novoselov
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.26808
UR  - https://arxiv.org/abs/2610.26808
AB  - In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~π’ͺ(n^4 q^3) operations in~𝔽_q, where~n is the length of the code and~q is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.
ER  -