THEMATIC PROGRAMS
April 19, 2024

Fall 2005
Renormalization and Universality in Mathematics and Mathematical Physics

Spring 2006
Holomorphic Dynamics, Laminations, and Hyperbolic Geometry

Computability and Complexity in Analysis and Dynamics Seminar
Fridays, 2:10 p.m.
Bahen Building, BA 026, 40 St. George Street

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 semi-algebraic 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 semi-algebraic 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
> 0$, we can do much more: not only to ``kill" all the
derivatives at once, but to bound uniformly the {\it analytic complexity} of the pieces, while their number remains of order $log \ ({1\over \delta})$. In contrast with the $C^k$-case, the number of pieces in an {\it analytic} reparametrization {\it cannot be bounded through the degree only}, and the above result is, essentially, sharp.

Relations to the Bernstein type inequalities for algebraic functions, as well as some new open questions concerning the complexity of semi-algebraic 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 non-uniform 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 non-uniform 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*

Jean-Pierre Dedieu, Université Paul Sabatier, Toulouse, France.
About the low-rank approximation problem
The low-rank approximation problem is to find the closest matrix with given (and low) rank from a given matrix. In some cases both the given matrix and its approximation are submitted to certain constraints. In this talk we study the geometry of this problem and we described a dynamical system associated with.
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 time-bounded 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 computer-assisted 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 finite-state 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 area-preserving homeomorphism of the 2-torus whose dynamics they proved to have several chaotic properties, e.g. it is mixing and has positive Lyapunov exponent. The chaos is non-uniform, 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 "pseudo-Anosov", which allows one to deduce several more properties and to quantify the singular behaviour. This is achieved by reduction to a finite-state automaton.
Sept. 30

Mark Braverman, University of Toronto
Introduction to real computation
Abstract: In this introductory talk we will discuss basic concepts of real computation theory. In particular, we will define the computability and complexity of real functions and subsets of R^n. We will present some recent results about the computability and complexity of Julia sets in this context. No prior knowledge about the area will be assumed.

Back to Thematic Program Index


back to top