Binary decoding · Binary · full GV distance

Binary · full GV distance

Binary random linear codes; full Gilbert–Varshamov distance; maximum over rates

10 results · 6 papers

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

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Decoding Linear Codes with High Error Rate and its Impact for LPN SecurityLeif Both · Alexander MayPQCrypto 2018Source BibTeX / details	27 Nov 2017	2^{0.0885 n + o(n)}	2^{0.0736 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.0926 n + o(n)}	2^{0.0647 n + o(n)}	PublishedSource checked
3	On Computing Nearest Neighbors with Applications to Decoding of Binary Linear CodesAlexander May · Ilya OzerovEurocrypt 2015Source BibTeX / detailsclassical ISD binary random codes full GV distance maximum over rates	26 Apr 2015	2^{0.097 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.0982 n + o(n)}	2^{0.0717 n + o(n)}	PublishedSource checked
5	Asymptotics and Improvements of Sieving for CodesLéo Ducas · Andre Esser · Simona Etinski · Elena KirshanovaEurocrypt 2024Source BibTeX / details	18 Mar 2024	2^{0.101 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 / detailsclassical ISD binary random codes full GV distance maximum over rates	20 Jan 2012	2^{0.102 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.1114 n + o(n)}	—	PublishedSource checked
8	On Computing Nearest Neighbors with Applications to Decoding of Binary Linear CodesAlexander May · Ilya OzerovEurocrypt 2015Source BibTeX / detailsclassical ISD binary random codes full GV distance maximum over rates	26 Apr 2015	2^{0.114 n + o(n)}	—	PublishedSource checked
9	Asymptotics and Improvements of Sieving for CodesLéo Ducas · Andre Esser · Simona Etinski · Elena KirshanovaEurocrypt 2024Source BibTeX / details	18 Mar 2024	2^{0.117 n + o(n)}	—	PublishedSource checked
10	The use of information sets in decoding cyclic codesEugene PrangeIRE Trans. Information Theory 1962Source BibTeX / details	1962	2^{0.1207 n + o(n)}	poly(n)	PublishedSource checked

Comparison definition & assumptions

Regime: Binary random linear codes; full Gilbert–Varshamov distance; maximum over rates
Computation: Classical
Rigor: Source analysis
Instances: Random binary linear codes
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Historical full-distance ISD bounds, separate from the bounded half-distance convention.
Comparison rules: Use random binary linear codes of rate R=k/n, error weight n H₂⁻¹(1−R), and maximize the exponent over 0≤R≤1. The parameter n is code length. Keep half-distance and fixed-rate bounds separate. Historical coefficients are rounded as in their cited sources; they are upper bounds, not claimed optimal values.
Tags: classical, ISD, binary, random codes, full GV distance, maximum over rates