This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL). ... more >>>

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

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