<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; ">CO-SPONSORED BY TTI-C & 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 4, 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; ">Speaker: Andrej Bogdanov</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">From:<span class="Apple-tab-span" style="white-space:pre"> </span>Tsinghua University</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; ">Web page: <a href="http://itcs.tsinghua.edu.cn/postodc/andrej.html">http://itcs.tsinghua.edu.cn/postodc/andrej.html</a></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; "><span style="">Title:</span><span style="color: black; "> </span><span style="">Pseudorandom bits for
polynomials</span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">
<div class="MsoNormal"><span style=""> <o:p></o:p></span></div><p class="MsoNormal" style="mso-pagination:none;mso-layout-grid-align:none;
text-autospace:none">Abstract: <span style="">Despite
our general belief that randomized computations can be simulated
deterministically in an efficient way, there are relatively few models for
which results of this type can be shown unconditionally. On the other hand, the
study of derandomization in simple models of computation has proved fruitful
even in domains where no applications were apparent at the outset.<o:p></o:p></span></p><p class="MsoNormal" style="mso-pagination:none;mso-layout-grid-align:none;
text-autospace:none"><span style=""> <o:p></o:p></span></p><p class="MsoNormal" style="mso-pagination:none;mso-layout-grid-align:none;
text-autospace:none"><span style="">We
consider pseudorandom generators for the class of low-degree multivariate
polynomials over a finite field. For degree 1 polynomials (linear functions),
such pseudorandom generators were first constructed by Naor and Naor in 1989
and have been widely studied and used ever since. In this talk we will discuss
some recent progress in constructing pseudorandom generators for higher degree
polynomials, and connections with other problems in computational complexity
and arithmetic combinatorics.<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"><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: Laszlo 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>