Ran Raz, Ph.D.Professor, Theoretical Computer Science, Princeton University
Weizmann Institute of Science
Simons Foundation Lectures are free public colloquia related to basic science and mathematics. These high-level talks are intended for professors, students, postdocs and business professionals, but interested people from the metropolitan area are welcome as well.
Can one prove unconditional lower bounds on the number of samples needed for learning, under memory constraints? A recent line of works shows that for a large class of learning problems, any learning algorithm requires either a memory of super-linear size or a super-polynomial number of samples. For example, any algorithm for learning parities of size n, from a stream of samples, requires either a memory of quadratic size or an exponential number of samples.
A main message of these works is that for some learning problems, access to a relatively large memory is crucial. Ran Raz will tell about some of these works and discuss relations to computational complexity and applications in bounded-storage cryptography.