Binary decoding / Binary · half distance

Decoding Random Linear Codes in Õ(2^{0.054n})

Alexander May · Alexander Meurer · Enrico Thomae

Asiacrypt 2011

PublishedSource checked

Time bound: 2^{0.0537 n + o(n)}
Space bound: —

Source / version date: 2011
Comparison variant: Binary · half distance
Cost scale: 2^{c n + o(n)}

Assumptions and source notes

Half-GV coefficient corroborated by the successor abstract.

Source location

Abstract
Version: 2012-01-20

Primary source ↗

BibTeXDownload .bib

@misc{mmt2011,
  author = {Alexander May and Alexander Meurer and Enrico Thomae},
  title = {{Decoding Random Linear Codes in Õ(2^{0.054n})}},
  year = {2011},
  url = {https://www.iacr.org/archive/asiacrypt2011/70730106/70730106.pdf},
  cr_date = {2011-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {ASIACRYPT 2011},
  cr_author_ids = {alexander-may; alexander-meurer; enrico-thomae}
}