Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SHAYAN OVEIS GHARAN:
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

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 >>>


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

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 >>>




ISSN 1433-8092 | Imprint