|October 21, 2014|
|Friday, 5 May 2006 at 2:10PM
BA6183, 40 St. George Street
** (note special location)
|Yosef Yomdin, The Weizmann Institute
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
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
|Friday, 31 March 2006 at 2:30PM *unusual time*||
Jean-Pierre Dedieu, Université Paul Sabatier,
|March 17, 2006||Peter Zograf, Steklov Mathematical
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
|Feb. 10, 2006||Alex Nabutovsky, University of
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
Computational Complexity of Julia Sets
|Wed., Nov. 2
** to be held at Fields Institute, 230
|Hans Koch (Uni)
A computer-assisted proof of a fixed point theorem in dynamics
** to be held at Fields Institute, Library
|Peter Hertling, Universitat der
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.
Mark Braverman, University of Toronto