LPN / Decision · fixed noise · unlimited samples

Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model

Avrim Blum · Adam Kalai · Hal Wasserman

STOC 2000

PublishedSource checked

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

Source / version date: 15 Oct 2000
Comparison variant: Decision · fixed noise · unlimited samples
Cost scale: limsup log₂(T) log₂(n) / n
Input samples: 2^{O(n/log₂ n)}
Model / assumptions: Independent Bernoulli noise with constant probability below 1/2

Assumptions and source notes

Original search algorithm also gives a decision bound; no numeric constant is inferred from Big-O.

Source location

Introduction, p. 2; §3
Version: arXiv:cs/0010022v1, submitted 15 October 2000

Primary source ↗

BibTeXDownload .bib

@inproceedings{bkw2000-noise-tolerant,
  author = {Avrim Blum and Adam Kalai and Hal Wasserman},
  title = {{Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model}},
  booktitle = {Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing},
  year = {2000},
  pages = {435--440},
  publisher = {ACM},
  url = {https://arxiv.org/abs/cs/0010022},
  keywords = {LPN, BKW, subexponential algorithms},
  cr_date = {2000-10-15},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {STOC 2000; Journal of the ACM 50(4), 2003},
  cr_author_ids = {avrim-blum; adam-kalai; hal-wasserman},
  archiveprefix = {arXiv},
  eprint = {cs/0010022},
  note = {Journal version: Journal of the ACM 50(4):506--519, 2003, doi:10.1145/792538.792543}
}