<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 </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; ">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: Friday, February 15, 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: Mark Braverman</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"> </font></span><font class="Apple-style-span" color="#272727">University of Toronto</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:/www/cs/toronto.edu/~mbraverm/</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); ">Computability
and Complexity of Julia sets</span></font></span></div>
<!--StartFragment-->
<!--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); ">Studying dynamical systems is key to
understanding a wide range of phenomena ranging from planets' movement to
climate patterns to market dynamics. Various numerical tools have been
developed to address specific questions about dynamical systems, such as predicting
the weather or planning the trajectory of a satellite. However, the theory of
computation behind these problems appears to be very difficult to develop.
While we have vast knowledge about computability and complexity of discrete
problems, little is known about computability of even the most natural problems
arising from dynamical systems. </span></font></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="font-family: Helvetica; color: black; ">The focus of our study is dynamical systems
that arise from iterating quadratic polynomials on the complex plane. They give
rise to the amazing variety of fractals known as Julia sets, and are closely
connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects
in Mathematics due to their fascinating fractal structure. The theory behind
them is even more fascinating, and the dynamical systems generating them are in
many ways archetypal.<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="font-family: Helvetica; color: black; ">In this talk we discuss what it means for a
planar set to be computable. We then present a variety of recent results, both
positive and negative, on the computability and complexity of Julia sets. In
particular we show that while the vast majority of Julia sets are computable -
many even in polynomial time, some are as hard to compute as the Halting
Problem and will never be drawn. The work paves the way to understanding
computational properties of more complicated dynamical systems.</span></p>
<!--EndFragment-->
<!--StartFragment-->
<!--EndFragment-->
<!--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>