63 citations · 124 across the 20 of their papers we have counts for
Showing cs.LGShow all
3 papers · 1 filter
cs.LG2021★ 2 cited
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 from a stream of random linear…
cs.LG2017
Extractor-Based Time-Space Lower Bounds for Learning
Sumegha Garg, Ran Raz, Avishay Tal
A matrix corresponds to the following learning problem: An unknown element is chosen uniformly at random. A learner tries to learn $x…
cs.LG2016★ 16 cited
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Ran Raz
We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Val…