Binary decoding · Binary · half distance

Binary · half distance

Half-distance decoding; worst asymptotic rate

8 results · 6 papers

ClassicalAsymptotic analysisRandom binary codes2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation TechniqueYang LiInformation 2025Source BibTeX / detailsheuristic	12 Oct 2025	2^{0.0453 n + o(n)}	—	PublishedSource checked
2	Decoding Linear Codes with High Error Rate and its Impact for LPN SecurityLeif Both · Alexander MayPQCrypto 2018Source BibTeX / details	27 Nov 2017	2^{0.0465 n + o(n)}	2^{0.0294 n + o(n)}	PublishedSource checked
3	On Computing Nearest Neighbors with Applications to Decoding of Binary Linear CodesAlexander May · Ilya OzerovEurocrypt 2015Source BibTeX / details	26 Apr 2015	2^{0.0473 n + o(n)}	—	PublishedSource checked
4	Decoding Linear Codes with High Error Rate and its Impact for LPN SecurityLeif Both · Alexander MayPQCrypto 2018Source BibTeX / details	27 Nov 2017	2^{0.0478 n + o(n)}	2^{0.029 n + o(n)}	PublishedSource checked
5	Decoding Linear Codes with High Error Rate and its Impact for LPN SecurityLeif Both · Alexander MayPQCrypto 2018Source BibTeX / details	27 Nov 2017	2^{0.0488 n + o(n)}	2^{0.029 n + o(n)}	PublishedSource checked
6	Decoding Random Binary Linear Codes in 2^(n/20): How 1+1=0 Improves Information Set DecodingAnja Becker · Antoine Joux · Alexander May · Alexander MeurerEurocrypt 2012Source BibTeX / details	20 Jan 2012	2^{0.0494 n + o(n)}	—	PublishedSource checked
7	Decoding Random Linear Codes in Õ(2^{0.054n})Alexander May · Alexander Meurer · Enrico ThomaeAsiacrypt 2011Source BibTeX / details	2011	2^{0.0537 n + o(n)}	—	PublishedSource checked
8	Smaller decoding exponents: ball-collision decodingDaniel J. Bernstein · Tanja Lange · Christiane PetersCrypto 2011Source BibTeX / details	7 Mar 2011	2^{0.0556 n + o(n)}	—	PublishedSource checked

Comparison definition & assumptions

Regime: Half-distance decoding; worst asymptotic rate
Computation: Classical
Rigor: Asymptotic analysis
Instances: Random binary codes
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Classical information-set decoding in the half-distance convention used by the cited asymptotic papers.
Comparison rules: n is binary code length. Use half the Gilbert–Varshamov distance and the paper’s worst-rate convention. Full-distance decoding, fixed-rate instances, q-ary decoding, and quantum ISD require their own categories. These are historical reference bounds, not a complete current leaderboard.
Tags