[Colloquium] Talk by Mark Braverman, University of Toronto on Today - Reminder

[Nita Yack]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, February 15, 2008
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th St.

-------------------------------------------

Speaker:  Mark Braverman

From:	University of Toronto

Web page:  http:/www/cs/toronto.edu/~mbraverm/

Title: Computability and Complexity of Julia sets

Abstract:  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.

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.

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.

  ****************************

Host:  Laci Babai





***********************************************************************************************************************************

Nita

**************************
Nita Yack
Departmental Administrator
Computer Science Department
1100 E. 58th Street - Room 151
Chicago, IL 60637
(773) 702-6019
(773) 702-8487 FAX

"Hard work spotlights the character of people: some turn up their  
sleeves, some turn up their noses, and some don't turn up at all."


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080215/b4076e9a/attachment.html