Memory-Sample Lower Bounds for Learning Parity with Noise

Sumegha Garg, Pravesh K. Kothari, Pengda Liu +1

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn $x=(x_1,\dots ,x_n)\in \{0,1{\}}^n$ from a stream of random linear…