All reports by Author Shayan Oveis Gharan:

__
TR18-114
| 6th June 2018
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

__
TR17-120
| 31st July 2017
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Revisions: 1

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>>

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 the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>