Learning Parity with Noise
Recover a binary secret from uniformly random binary linear equations corrupted by independent Bernoulli noise.
7 variants · 11 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
LPNClassical · memory coefficient ≤ 1/2Classical · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scaleUniform random equations31.807355 LPNClassical · memory coefficient ≤ 2/3Classical · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scaleUniform random equations21.333333 LPNDecision · fixed noise · unlimited samplesClassical · ProvableDecisional LPN; constant Bernoulli error probability 0 < p < 1/2; unlimited samplesUniform random equations21 LPNClassical · fixed noise · polynomial samplesClassical · ProvableConstant Bernoulli noise; n^{1+δ} samples for each fixed δ > 0Uniform random equations1— LPNClassical · noise probability 1/√nClassical · ProvableBernoulli error probability p = n^{-1/2}; unlimited fresh samplesUniform random equations11.442695 LPNQuantum · memory coefficient ≤ 1/2Quantum · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤1/2 on the n/log₂n scaleUniform random equations11.637624 LPNQuantum · memory coefficient ≤ 2/3Quantum · HeuristicConstant Bernoulli noise; limiting memory coefficient ≤2/3 on the n/log₂n scaleUniform random equations11.333333