Extractor-Based Time-Space Lower Bounds for Learning

Sumegha Garg, Ran Raz, Avishay Tal

A matrix $M:A\times X\to \{-1,1\}$ corresponds to the following learning problem: An unknown element $x\in X$ is chosen uniformly at random. A learner tries to learn $x…