Time-space hardness of learning sparse parities
Gillat Kol, Ran Raz, Avishay Tal · 2017
We define a concept class ℱ to be time-space hard (or memory-samples hard) if any learning algorithm for ℱ requires either a memory of size super-linear in n or a number of samples super-polynomial in n, where n is the length of one sample.