
THEMATIC PROGRAMS 

April 23, 2014  
Unless indicated otherwise, the seminars will take place in the
Fields Institute, Stewart Library from 23 pm. Past Talks

Wednesday 23 pm 
Bruno Grenet (visiting the Fields Institute from ENS Lyon) The resultant of a (generic) system of polynomials f_1,...,f_n is a polynomial in the indeterminate coefficients of the f_i which vanishes iff the f_i have a common root. In the case of two univariate polynomials, the resultant is the determinant of the Sylvester matrix and so is computable in polynomial time. The case we are interested in is a system of n homogenous polynomials in n variables. Canny gave in 1987 a PSPACE algorithm to compute the resultant in that case. We try to give a tighter estimation of the complexity. As an upper bound, we will show that the problem stands in fact in the polynomial hierarchy, namely in the class AM. As a lower bound, we'll show that it is NPhard. Canny's algorithm uses evaluation of exponential size determinants. If we have time, we will show that in a sense Canny's method cannot be improved, as in a general case computing such determinants in PSPACEcomplete. 
Thursday 
T.Y. Li (visiting Fields from Michigan State
University) Numerical Solutions of Polynomial Systems 
Wednesday 
Gregorio Malajovich (visiting Fields from Rio) Newton iteration on manifolds has attracted a lot of atention recently. Also, a proper choice of a Riemannian (or a LipschitzRiemann) structure seems to be a key step for efficient pathfollowing on manifolds. This talk is about Newton iteration on Riemannian manifolds. I will not consider the pathfollowing problem here. Instead, I will make the case for the following table for covariant Newton iteration on manifolds. Depends ? Newton Iteration alphatheory Newton iteration can be defined independently of the Riemann structure, up to first order. However, all of alphatheory is extremely dependent on the metric. For algorithmic purposes, we should therefore select the “best” metric in order to guarantee quadratic convergence in the largest possible domain. At second order, Newton iteration seems to depend from the metric. My point here is that this is the wrong notion. Newton iteration depends on a “chart”. Riemannian Newton iteration on manifolds uses the exponential map (i.e. a normal system of coordinates) to associate, to a vector at the last iterate, the next iterate. Many wellstudied variations of Newton iteration do not fit into the Rie mannian Newton framework. This is the case, for instance, of GaussNewton iteration in Interior Point Methods. We shall therefore extend alphatheory to encompass known examples. This extension is necessary. Riemannian Newton iteration asks for the computation or approximation of geodesics. Following geodesics is as hard as nonlinear equation solving (Theorem 26 below contains the precise state ment). 
Thursday 
Javier Pena (visiting Fields from
CMU) On the distance to illposedness 
Friday October 9, 2009 2:00 p.m. Room 230 
Special
Lecture Ragni Piene  University of Oslo Generating functions in enumerative geometry Abstract. I will explain some problems in enumerative algebraic geometry concerning the counting of curves. In certain cases, solutions exist in the form of explicit generating functions, in other cases there are only conjectures as to the shape of these functions. In particular, I will consider the case of nodal curves on an algebraic surface (joint work with Steve Kleiman). 
Wednesday 
Jean Lasserre (visiting Fields
from LAAS in France) Approximate volume and integration for basic semialgebraic sets 
Thursday 
Peter Scheiblechner CastelnuovoMumford Regularity and Computing the de Rham Cohomology of Smooth Projective Varieties 
Monday 
Bernd Bank Wavelet design via algorithmic real algebraic geometry 
Wednesday 
Ricky Pollack Most of this work is joint with Jacob E. Goodman and some involves numerous other people, among whom are Raghavan Dhandapani, Andreas Holmsen, Shakhar Smorodinsky, Rephael Wenger, and Tudor Zamfirescu. 
Thursday 
Michael Todd Linear convergence of modified FrankWolfe algorithms for ellipsoid optimization problems 
November
4, 2009 23 pm Stewart Library 
Jim Renegar. Optimization Over Hyperbolicity Cones Linear programming, secondorder programming and semidefinite programming are examples of optimization problems for which the underlying cones (the nonnegative orthant, the Lorentz cone, the cone of positive semidefinite matrices) are socalled hyperbolicity cones. All hyperbolicity cones are rich in a marriage of analytical structure and algebraic structure, far more than to date has been relied upon in designing optimization algorithms. We review highlights from the (small) optimization literature on hyperbolcity cones, suggest a couple of new algorithms that are naturally motivated by the hyperbolcity setting, sketch partial progress that has been made in analyzing the algorithms, and discuss where remain roadblocks to complete analyses. 
November 5,
2009 23 pm Stewart Library 
Dennis Amelunxen, Universität
Paderborn Geometric analysis of the condition of the convex feasibility problem We give an average analysis of Renegar's condition number that holds for any convex cone, in particular the semidefinite one. This is achieved by studying a new coordinatefree version of Renegar's condition number. Its analysis relies on a formula on the volume of tubes in Grassman manifolds in terms of the intrinsic volumes of the convex cone at hand. We will also indicate a way to obtain a smoothed analysis, which has yet to be worked out properly. 
Wednesday 23 pm 
Minh Ha Quang Vectorvalued reproducing kernel Hilbert spaces, with an application in image procesing Kernel methods have recently emerged as a powerful framework for many machine learning and data mining applications. In this talk, we will give an overview of the theory of operatorvalued positive definite kernels and their associated vectorvalued reproducing kernel Hilbert spaces (RKHS). An application in image colorization (of black and white images) will be presented. We will discuss the computational complexity of our framework, and questions related to the problem of learning manifoldvalued data. 
Thursday 23 pm 
Carles Simo On the regularity of the infinity manifolds: the case of Sitnikov problem and some global aspects of the dynamics One of the outstanding problems in Celestial Mechanics is the detection and computation of capture and escape boundaries. They are related to the existence of some invariant objects at infinity which have parabolic invariant manifolds. It is well known that this fact was partially analysed by Moser and McGehee in the case of the Sitnikov problem. The manifolds exists and they are analytic except, perhaps, at infinity. The result is related to symbolic dynamics, existence of interesting motions and chaos. In this work we proof that the manifold are ``exactly'' of class Gevrey1/3. Sharp enalyic estimates are provided. A computer implementation allows to obtain an easy and accurate description of the capture and escape boundaries. It is supplemented by information on the global dynamics of the problem. General considerations about the relation of this behaviour with exponentially small splitting of separatrices and also with interpolation and averaging theorems will close the presentation. 
Thursday 23 pm 
Diego Armentano Stochastic perturbations and smooth condition numbers In this talk we will introduce a condition number adapted to directionally uniform perturbations in a general framework of maps between Riemannian manifolds. We will show the relation with the classical condition number, and study some interesting examples. 
Wednesday 23 pm 
Teresa Krick This talk will present an ongoing work with Carlos D'Andrea and Martin Sombra, where we obtain precise bounds for the Effective Nullstellensatz in its Arithmetic aspects. The Nullstellensatz establishes that if f_1,...,f_s in Z[x_1,...,x_n] are polynomials with no common complex roots, then they satisfy a Bezout identity a=g_1f_1+...+g_sf_s for some integer polynomials g_1,...,g_s and some nonzero integer a. While the Effective Nullstellensatz consists in producing bounds for the degrees of such polynomials g_i's in case they exist in terms of the number of variables n and the degrees of the f_i's, the Arithmetic Nullstellensatz aims to also bound the heights (max log of absolute values of coefficients) of the g_i's and a, in terms of the heights of the f_i's too. I will discuss an Arithmetic Nullstellensatz that is obtained
by translating to the arithmetic setting (developing the needed
height machinery) a recent proof by Jelonek of the Effective
Nullstellensatz for the degrees which reduces the problem
to a classical Perron Theorem on the degree of an algebraic
dependence equations for n+1 polynomials over Q[x_1,...,x_n]. 
Thursday 23 pm 
Pascal Koiran A hitting set for a family F of polynomials is a (finite)
set of point such that a polynomial P in F vanishes at all
points of the hitting iff P is identically zero. Hitting sets
have applications to polynomial identity testing and arithmetic
circuit lower bounds. 