Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
Quantum · memory coefficient ≤ 1/2
Constant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scale
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Dissection-BKWCrypto 2018SourceBibTeX / detailsquantum heuristic LPN coherent reads | 2018 | 2((7/(2·6)) log₂(7)+ε) n/log₂ n | 2(log₂(7)/6+ε) n/log₂ n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Constant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scale
- Computation
- Quantum
- Rigor
- Heuristic
- Instances
- Uniform random equations
- Cost scale
- limsup log₂(T) log₂(n) / n
- Parameter
- n
- Description
- Constant Bernoulli noise; memory ≤ 2^{(1/2+o(1)) n/log₂ n}
- Comparison rules
- Compare the leading time coefficient at the stated subexponential memory cap. The c-sum methods use the Independence Heuristic; tailored rows additionally require the Tailoring Heuristic. Every fixed positive exponent slack is allowed. Quantum rows assume coherent indexed access to the stored list.
- Tags
- constant noise, time-memory tradeoff, independence heuristic, coherent reads