Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where…