Quasi-polynomial time algorithms for block basis reduction of linear codes

What it is

Kolesnikov and Novoselov, "Quasi-polynomial time algorithms for block basis reduction of linear codes" (ePrint 2026/2685, received 29 October 2026, a preprint). It modifies the block code basis reduction (BKZ) algorithm of Ghentiyala and Stephens-Davidowitz, which reduces a linear code basis using a minimum weight codeword (MWC) oracle on blocks of size β. The target problem is low-weight codeword search.

How it works

The paper states that the original algorithm's call bounds are exponential and, in almost all cases, worse than plain enumeration of codewords, even though the algorithm performs much better in practice. It offers three relaxations, each with a different guarantee:

1. Truncated BKZ: heuristic quasi-polynomial number of MWC-oracle calls for fixed β, with the same basis quality as full BKZ.
2. Basis restrictions: adding weak conditions on the code basis brings the call count down to polynomial.
3. DeepBKZ: adapted from lattice reduction. With relaxations analogous to PotBKZ for lattices, it also needs a quasi-polynomial number of calls.

Preconditions / Affected

All results are for fixed block size β. The quasi-polynomial bound for truncated BKZ is heuristic, not proven. The DeepBKZ bound depends on the PotBKZ-style relaxations.

Caveats

The page gives only the abstract, so it has no concrete exponents, no measured approximation factors and no runtime figures. The abstract says the implementation handles block sizes 2 to 24 "and more", and that it produced complexity estimates and approximation factors for random linear codes. The abstract does not say whether the code is public. Structured codes are not mentioned.