<div dir="ltr"><div class="gmail_default"><p class="gmail-m_-9044756020020464078gmail-m_-7290113535751474315gmail-m_1303750247107387153gmail-m_2825358517816514856gmail-m_5665334593080371447m_-3748643693577471394gmail-m_-4404257975496107222gmail-m_-7206066681144029448gmail-m_-5817829815640557222gmail-m_5987474974647831651gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_9103776001042077600gmail-p1" style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, helvetica, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">When:    </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Tuesday, May 7th at <b>11:00 am</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">Where:     </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, helvetica, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">Who:        </font></font></b><span class="gmail-m_-9044756020020464078gmail-il">Ran</span> <span class="gmail-m_-9044756020020464078gmail-il">Raz</span>, Princeton University</font>  <b style="font-family:arial,helvetica,sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"> </font></font></b></p></div><div class="gmail_default"><b style="color:rgb(33,33,33);font-size:13px"><br></b></div><div class="gmail_default"><b style="color:rgb(33,33,33);font-size:13px">Title:        </b><span style="font-family:arial,helvetica,sans-serif">Learning Fast Requires Good Memory: Time-Space Tradeoff Lower Bounds for Learning</span><b style="font-size:13px;color:rgb(33,33,33)">    </b></div><div class="gmail_default"><p class="gmail-m_-9044756020020464078gmail-m_-7290113535751474315gmail-m_1303750247107387153gmail-m_2825358517816514856gmail-m_5665334593080371447m_-3748643693577471394gmail-m_-4404257975496107222gmail-m_-7206066681144029448gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1"><b style="color:rgb(33,33,33)">Abstract:</b><font color="#212121"> </font><font color="#000000"><font face="arial, helvetica, sans-serif">Can one prove unconditional lower bounds on the number of samples </font><span style="font-family:arial,helvetica,sans-serif">needed for learning, under memory constraints? A recent line of </span><span style="font-family:arial,helvetica,sans-serif">works shows that for a large class of learning problems, any </span><font face="arial, helvetica, sans-serif">learning algorithm requires either a memory of super-linear size or </font><span style="font-family:arial,helvetica,sans-serif">a super-polynomial number of samples. For example, any algorithm </span><span style="font-family:arial,helvetica,sans-serif">for learning parities of size n, from a stream of samples, requires </span><font face="arial, helvetica, sans-serif">either a memory of quadratic size or an exponential number of </font><span style="font-family:arial,helvetica,sans-serif">samples.</span></font></p><div><font color="#000000"><font face="arial, helvetica, sans-serif">A main message of these works is that for some learning problems, </font><span style="font-family:arial,helvetica,sans-serif">access to a relatively large memory is crucial. I will tell about </span><span style="font-family:arial,helvetica,sans-serif">some of these works and discuss relations to computational </span><span style="font-family:arial,helvetica,sans-serif">complexity and applications in bounded-storage cryptography.</span></font></div><div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><p style="box-sizing:border-box;border-radius:0px;margin:0px 0px 10px;font-size:13px"><font color="#000000" face="arial, helvetica, sans-serif"><span style="box-sizing:border-box;border-radius:0px;font-weight:700">Bio:</span> <span class="gmail-m_-9044756020020464078gmail-il">Ran</span> <span class="gmail-m_-9044756020020464078gmail-il">Raz</span> is a professor of computer science at Princeton University. <span class="gmail-m_-9044756020020464078gmail-il">Raz</span> 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. <span class="gmail-m_-9044756020020464078gmail-il">Raz</span>’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.</font></p><p style="box-sizing:border-box;border-radius:0px;margin:0px 0px 10px;font-size:13px"><font face="arial, helvetica, sans-serif" color="#000000"><span style="box-sizing:border-box;border-radius:0px;font-weight:700">Host:</span> <a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev</a></font></p></div></div><div><br></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 518</i></div><div><font color="#0b5394"><i>Chicago, IL 60637</i></font></div></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div>