
THEMATIC PROGRAMS 

November 25, 2015  
Fall 2005

Friday, 5 May 2006 at 2:10PM BA6183, 40 St. George Street ** (note special location) 
Yosef Yomdin, The Weizmann Institute
of Science Analytic reparametrization of semialgebraic sets and local complexity bounds In many problems in Analysis and Dynamics it is important to subdivide objects under consideration into simple pieces, keeping control of high order derivatives. It is known that semialgebraic sets $A$ inside the unit ball allow for a $C^k$  triangulation, where each simplex is represented as an image, under the ``reparametrization mapping" $\psi$, of the standard simplex, with all the derivatives of $\psi$ up to order $k$ bounded by $1$. The number of simplices in this triangulation is bounded through the degree of $A$. The main result presented in this talk is, that
if we reparametrize all the set $A$ but its small part of a size
$\delta Relations to the Bernstein type inequalities for algebraic functions, as well as some new open questions concerning the complexity of semialgebraic sets will be stressed. Initial applications in Analytic Dynamics will be discussed, in particular, explicit bounds on the local volume growth in iterations of analytic mappings. 
Friday, 21 April 2006 at 10:10AM ** to be held at Fields Institute, Library *unusual time and location* 
Vasco Brattka, University of Cape
Town via videoconference Plottable real number functions and the computable graph theorem The Graph Theorem of classical recursion theory states that a total function on the natural numbers is computable, if and only if its graph is recursive. It is known that this result can be generalized to real number functions where it has an important practical interpretation: the total computable real number functions are precisely those which can be effectively plotted with any given resolution. We generalize the Graph Theorem to appropriate partial real number functions and even further to functions defined on certain computable metric spaces. Besides the nonuniform version of the Graph Theorem which logically relates computability properties of the function and computability properties of its graph, we also discuss the uniform version: given a program of a function, can we algorithmically derive a description of its graph? And, vice versa, given a description of the graph, can we derive a program of the function? While the passage from functions to graphs always is computable, the inverse direction from graphs to functions is problematic and it turns out that the answers to the uniform and the nonuniform questions do not coincide. We prove that in both cases certain topological and computational properties (such as compactness or effective local connectedness) are sufficient for a positive answer and we provide counterexamples which show that the corresponding properties are not superfluous. Additionally, we briefly discuss the special situation of the linear case. 
Apr. 7  Alex Nabutovsky, University of
Toronto Title: tba 
Friday, 31 March 2006 at 2:30PM *unusual time* 
JeanPierre Dedieu, Université Paul Sabatier,
Toulouse, France. 
March 17, 2006  Peter Zograf, Steklov Mathematical
Institute, St.Petersburg Symmetric tensors and enumeration of Hamiltonian cycles in graphs 
3 March 2006 ** (note time change to 3:10)** 
Dierk Schleicher, International
University of Bremen On Newton's Method for Polynomials in One Variable: Conformal Dynamics meets Complexity. We discuss the famous Newton method for finding roots of holomorphic functions in one variable, with a special emphasis on polynomials (and some transcendental functions). We present a very small explicit set of starting points from which one can find all roots of a polynomial, and we discuss bounds on how efficient this method is. 
Feb. 10, 2006  Alex Nabutovsky, University of
Toronto Kolmogorov complexity and some of its applications to geometry Abstract: I will explain the notions of Kolomogorov complexity and timebounded Kolmogorov complexity of decision problems. These concepts turn out to be relevant for geometry, in particular, for study of critical points of Riemannian functionals (= functionals on spaces of isometry classes of Riemannian metrics on compact manifolds). 
Feb. 3  Michael Shub, University of Toronto
Good starting points for solving systems of polynomial equations and Smale's 17th Problem Abstract: In what sense can a system of n homogeneous polynomials in n + 1 complex variables, which may have exponentially many roots in its input size, be solved in polynomial time? 
Nov. 25  Michael Yampolsky (University of
Toronto) Computational Complexity of Julia Sets 
Wed., Nov. 2 ** to be held at Fields Institute, 230 
tba 
Oct. 28 
Hans Koch (Uni) A computerassisted proof of a fixed point theorem in dynamics 
Oct. 14 ** to be held at Fields Institute, Library 
Peter Hertling, Universitat der
Bundeswehr Munchen Topological Complexity of Zero Finding for Continuous Functions Abstract: The topological complexity of a problem over the real numbers is the minimum number of tests or comparisons that one needs to perform in order to solve the problem. One can consider topological complexity in various settings. It has turned out that the topological complexity of a problem can be very different depending on the set of operations which, besides comparisons, are allowed for its solution: either only algebraic operations, or also other operations like exp, log, absolute value, or even all continous operations, which is the purely topological setting. In the purely topological setting the topological complexity can be characterized also as a degree of discontinuity. It is closely related to the Schwarz genus, and one is led to problems involving algebraic topology, investigated by Smale and Vassiliev. Computational problems in various fields give rise to an investigation in topological complexity, namely algebraic complexity theory, numerical computation, and computational geometry. For example in computational geometry the topological complexity of a problem can be considered as a measure of the degree of degeneracy of the degenerate input configurations, i.e., those configurations where the output values or some values computed during the solution process show a discontinuity. In this talk we give an introduction to topological complexity. After presenting fundamental definitions and results, we will focus on results concerning the topological complexity of various versions of the problem to approximate zeros of univariate functions on the unit interval, studied by Novak and Wozniakowski and by the speaker. 
Oct. 7  Robert MacKay, University of Warwick
Dynamics of a piecewise affine homeomorphism of the torus Abstract: The simplest forms of chaos in dynamical systems are those which are equivalent to finitestate automata. Yet it is not always obvious when this can be done, nor what are the probabilistic consequences. Cerbelli and Giona introduced an interesting example of a piecewise affine areapreserving homeomorphism of the 2torus whose dynamics they proved to have several chaotic properties, e.g. it is mixing and has positive Lyapunov exponent. The chaos is nonuniform, however: the invariant manifolds fold on themselves infinitely often in opposite directions and fill out the torus in a singular way, so they thought this was different from standard types of chaos. Nevertheless, I show it is "pseudoAnosov", which allows one to deduce several more properties and to quantify the singular behaviour. This is achieved by reduction to a finitestate automaton. 
Sept. 30 
Mark Braverman, University of Toronto 