[Colloquium] REMINDER: 5/7 TTIC Distinguished Lecture Series: Ran Raz, Princeton University

[Alicia McClarin]

*When:    *  Tuesday, May 7th at *11:00 am*



*Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who:        *Ran Raz, Princeton University

*Title:        *Learning Fast Requires Good Memory: Time-Space Tradeoff
Lower Bounds for Learning

*Abstract:* 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. I will tell about some of these works
and discuss relations to computational complexity and applications in
bounded-storage cryptography.

Bio: Ran Raz is a professor of computer science at Princeton
University. Raz received
his B.Sc. in mathematics and physics (1987) and Ph.D. in mathematics (1992)
from the Hebrew University of Jerusalem. After a post-doctoral fellowship
at Princeton he joined the faculty at the Weizmann Institute of Science. He
was a visiting professor at the Institute for Advanced Study and at
Microsoft Research. Raz’s main research area is complexity theory, with a
focus on proving lower bounds for computational models. More specifically,
he is interested in Boolean and arithmetic circuit complexity,
communication complexity, probabilistically checkable proofs, quantum
computation and communication, and randomness and derandomization.

Host: Yury Makarychev <yury at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 518*
*Chicago, IL 60637*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190507/812506b8/attachment.html>