<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">DEPARTMENT OF COMPUTER SCIENCE - TALK </div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><br class="khtml-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">SPONSORED BY UNIVERSITY OF CHICAGO</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 12px/normal Helvetica; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Date: Monday, February 11, 2008</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Time: 2:30 p.m.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Place: Ryerson 251, 1100 E. 58th St.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 12px/normal Helvetica; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">-------------------------------------------</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727">Speaker: Emanuele Viola</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727"><br></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727">From:</font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" color="#272727"> Columbia </font></span><font class="Apple-style-span" color="#272727">University</font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727"><br class="webkit-block-placeholder"></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727">Web page: </font><a href="http://lmi.bwh.harvard.edu/~gk/"><font class="Apple-style-span" color="#272727">http://www1.cs.columbia.edu/~viola/</font></a></div>
<!--StartFragment-->
<!--EndFragment-->
<div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><font class="Apple-style-span" color="#272727"><br class="webkit-block-placeholder"></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span style=""><font class="Apple-style-span" color="#272727">Title: <span class="Apple-style-span" style="color: rgb(0, 0, 0); ">Lower Bounds and the Power of Randomness</span></font></span></div>
<!--StartFragment--><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">
<div class="MsoNormal"><span style=""><font class="Apple-style-span" color="#272727"> </font><font class="Apple-style-span" color="#272727"><o:p></o:p></font></span></div><p class="MsoNormal" style="mso-pagination:none;mso-layout-grid-align:none;
text-autospace:none"><font class="Apple-style-span" color="#272727">Abstract: <span class="Apple-style-span" style="color: rgb(0, 0, 0); font-family: Verdana; font-size: 11px; ">Computation is an ubiquitous phenomenon in nature, and of increasing relevance to many fields such as economics, biology, and mathematics. In this talk we survey some of our results in two surprisingly interrelated areas that are central to the understanding of computation: lower bounds and the power of randomness.</span></font></p><span class="Apple-style-span" style="font-family: Verdana; font-size: 11px; "><p style="font-family: Verdana, arial, sans-serif; font-size: 11px; color: rgb(0, 0, 0); margin-top: 5px; margin-bottom: 20px; ">In particular, we consider the fundamental problem of following a path in a graph whose edges are distributed among several collaborating players. We obtain a lower bound on the amount of communication that the players need to exchange, answering a decade-old question. We also consider the problem of constructing sequences of bits that ``look random'' though being generated with little or no randomness. Here we present a pseudorandom generator that stretches few random bits into a long sequence which looks random to polynomials. Our result marks the first progress on this problem since 1993, and has spurred interaction between computer scientists and mathematicians, leading to advances on an outstanding conjecture in combinatorics.</p></span>
<!--StartFragment-->
<!--EndFragment-->
<p class="MsoNormal" style="mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt;
mso-layout-grid-align:none;text-autospace:none"><span style="color: black; "> ****************************<o:p></o:p></span></p><p class="MsoNormal" style="mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt;
mso-layout-grid-align:none;text-autospace:none">Host: Laci Babai</p><p class="MsoNormal" style="mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt;
mso-layout-grid-align:none;text-autospace:none"><br class="webkit-block-placeholder"></p><p class="MsoNormal" style="mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt;
mso-layout-grid-align:none;text-autospace:none"><br class="webkit-block-placeholder"></p><p class="MsoNormal" style="mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt;
mso-layout-grid-align:none;text-autospace:none">***********************************************************************************************************************************</p>
<!--EndFragment-->
</div><div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">Nita</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px"><br></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">**************************</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">Nita Yack</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">Departmental Administrator</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">Computer Science Department</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">1100 E. 58th Street - Room 151</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">Chicago, IL 60637</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">(773) 702-6019</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font face="Helvetica" size="3" style="font: 12.0px Helvetica">(773) 702-8487 FAX</font></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><br class="khtml-block-placeholder"></p><p style="margin: 0.0px 0.0px 0.0px 0.0px"><font class="Apple-style-span" face="Arial" size="4"><span class="Apple-style-span" style="font-size: 16px;; font-family: Arial; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; ">"Hard work spotlights the character of people: some turn up their </span></span></span></font><font class="Apple-style-span" face="Arial" size="4"><span class="Apple-style-span" style="font-size: 16px;; font-family: Arial; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; ">sleeves, some turn up their noses, and </span></span></span></font><font class="Apple-style-span" face="Arial" size="4"><span class="Apple-style-span" style="font-size: 16px;; font-family: Arial; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; "><span class="Apple-style-span" style="font-family: Arial; font-size: 16px; ">some don't turn up at all."</span></span></span></font></p><br class="Apple-interchange-newline"></span></div></span> </div><br></body></html>