Learning Sparse Parity with Noise in Linear Samples

We revisit the learning parity with noise problem with a sparse secret that involves at most k out of n variables. Let η denote the noise rate such that each label gets flipped with probability η. In this work, we show algorithms in the low-noise setting and high-noise setting separately. We present an algorithm of running time O(η · n/k)ᵏ for any η and k satisfying n>k/η. This improves the state-of-the-art for learning sparse parity in a wide range of parameters like k≤ n0.99 and η < √k/n, where the best known algorithm had running time at least nk/2 ≥ (n/k)k/2 . Different from previous approaches based on generating biased samples , our new idea is to combine subset sampling and Gaussian elimination. The resulting algorithm just needs O(k/η + k log n/k) samples and is structurally simpler than previous algorithms. In the high-noise setting, we present an improvement on Valiant's classical algorithm using nω+o(1)/3· k time (with the matrix multiplication constant ω) and Õ(k²) samples. For any η<1/2, our algorithm has time complexity (n/k)ω+o(1)/3· k and sample complexity Õ(k). Hence it improves Valiant's algorithm in terms of both time complexity and sample complexity and generalizes Valiant's framework to give the state-of-the-art bound for any k ≤ n0.99 and η ∈ (0.4,0.5).