<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceType"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceName"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
p
{mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman";}
span.EmailStyle18
{mso-style-type:personal;
font-family:Arial;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle20
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle21
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle22
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle23
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle24
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle25
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle26
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>When:
Friday, April 11 @ 10:00am<b><span style='font-weight:bold'><o:p></o:p></span></b></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Where:
TTI-C Conference Room<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p style='margin:0in;margin-bottom:.0001pt'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Who:
Mark Braverman, <st1:place w:st="on"><st1:PlaceType w:st="on">University</st1:PlaceType>
of <st1:PlaceName w:st="on">Toronto</st1:PlaceName></st1:place><o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Topic:
Computability and Complexity of Julia sets<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>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.<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>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></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>In this talk we discuss what it
means for a planar set to be computable.<font color=navy><span
style='color:navy'> </span></font>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.<font
color=navy><span style='color:navy'><o:p></o:p></span></font></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Contact:
Nikhil Devanur,
TTI-C nikhil@tti-c.org
834-3541 <o:p></o:p></span></font></p>
<p style='margin:0in;margin-bottom:.0001pt'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'> <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
</div>
</body>
</html>