LPN / Classical · fixed noise · polynomial samples

The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem

Vadim Lyubashevsky

APPROX/RANDOM 2005

PublishedSource checked

Time bound: 2^{O(n/log₂ log₂ n)}
Space bound: Not separately normalized

Source / version date: 2005
Comparison variant: Classical · fixed noise · polynomial samples
Cost scale: 2^{O(n / log₂ log₂ n)}
Input samples: n^{1+δ}, fixed δ>0
Model / assumptions: Sample amplification analyzed with the leftover hash lemma
Exact coefficient / bound: Big-O exponent retained

Assumptions and source notes

Any fixed sample exponent δ>0; constant noise is a specialization of the stated bias range.

Source location

Abstract; §2, Theorem 1
Version: RANDOM 2005 extended abstract, 12 pages

Selected earlier references

Selected sources cited by this paper.

Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum · Adam Kalai · Hal Wasserman · 2000
Answers the earlier question about subexponential LPN with polynomially many examples. Introduction and reference [2]

Primary source ↗

BibTeXDownload .bib

@inproceedings{lyubashevsky2005-parity-noise,
  author = {Vadim Lyubashevsky},
  title = {{The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem}},
  booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques},
  year = {2005},
  volume = {3624},
  pages = {378--389},
  publisher = {Springer},
  doi = {10.1007/11538462_32},
  url = {https://doi.org/10.1007/11538462_32},
  keywords = {LPN, sample amplification, polynomial samples},
  cr_date = {2005-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {APPROX/RANDOM 2005, LNCS 3624},
  cr_author_ids = {vadim-lyubashevsky},
  series = {Lecture Notes in Computer Science}
}