Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Classical · fixed noise · polynomial samples
Constant Bernoulli noise; n^{1+δ} samples for each fixed δ > 0
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum ProblemAPPROX/RANDOM 2005SourceBibTeX / detailsclassical provable LPN polynomial samples | 2005 | 2O(n/log₂ log₂ n) | Not separately normalized | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Constant Bernoulli noise; n^{1+δ} samples for each fixed δ > 0
- Computation
- Classical
- Rigor
- Provable
- Instances
- Uniform random equations
- Cost scale
- 2^{O(n / log₂ log₂ n)}
- Parameter
- n
- Description
- Constant Bernoulli noise; n^{1+δ} samples for each fixed δ > 0
- Comparison rules
- Compare bounds only under the displayed noise, sample and memory conditions.
- Tags
- constant noise, polynomial samples, sample amplification