[FOM] Julia sets and computability models

[Stephen Cook]

I would like to draw attention to several recent papers on
computability and complexity in analysis, authored or coauthored
by my PhD student Mark Braverman.  These papers are available
on Mark's web site at
    http://www.cs.toronto.edu/~mbraverm/

"On the complexity of real functions" is a very nice survey paper
comparing various "bit complexity" models and variations on the
Blum/Shub/Smale model of computation, both for computing real functions
and recognizing (or "drawing") subsets of R^n, such as the Mandelbrot set.

"Filled Julia sets with empty interior are computable" and
"On computational complexity of Siegel Julia sets", coauthored
with Ilia Binder and Michael Yampolsky,  come close to
classifying all Julia sets with respect to computabililty, using
recent deep theorems in dynamical systems.

Mark's MSc thesis (also available) compares computational models,
and proves that all hyperbolic Julia sets are polynomial time computable
(using a standard computation model based on "drawing" arbitrarily
fine details of the set), a result proved independently by R. Rettinger.

Stephen Cook