Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Decision · fixed noise · unlimited samples
Decisional LPN; constant Bernoulli error probability 0 < p < 1/2; unlimited samples
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | An Improved BKW Algorithm for LWE with Applications to Cryptography and LatticesCrypto 2015SourceBibTeX / detailsclassical provable LPN BKW | 29 Jun 2015 | 2(1+o(1)) n/log₂ n | 2(1+o(1)) n/log₂ n | PublishedSource checked |
| — | Noise-Tolerant Learning, the Parity Problem, and the Statistical Query ModelSTOC 2000SourceBibTeX / detailsclassical provable LPN BKW | 15 Oct 2000 | 2O(n/log₂ n) | 2O(n/log₂ n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Decisional LPN; constant Bernoulli error probability 0 < p < 1/2; unlimited samples
- Computation
- Classical
- Rigor
- Provable
- Instances
- Uniform random equations
- Cost scale
- limsup log₂(T) log₂(n) / n
- Parameter
- n
- Description
- Decisional LPN; constant Bernoulli error probability 0 < p < 1/2; unlimited samples
- Comparison rules
- Compare bounds only under the displayed noise, sample and memory conditions.
- Tags
- constant noise, unlimited samples, subexponential