THEMATIC PROGRAMS

August  1, 2014

Thematic Program on the Foundations of Computational Mathematics

Program Visitors Seminar Series

Unless indicated otherwise, the seminars will take place in the Fields Institute, Stewart Library from 2-3 pm.
Please subscribe to the Fields mail list to be informed of upcoming seminars.

Past Talks

Wednesday
September 30, 2009

2-3 pm
Stewart Library

Bruno Grenet (visiting the Fields Institute from ENS Lyon)
Hardness of the resultant

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 NP-hard.

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 PSPACE-complete.

Thursday
October 1, 2009
2-3 pm
Stewart Library

T.-Y. Li (visiting Fields from Michigan State University)
Numerical Solutions of Polynomial Systems

Wednesday
October 7, 2009
2-3 pm
Stewart Library

Gregorio Malajovich (visiting Fields from Rio)
Newton Iteration on Manifolds

Newton iteration on manifolds has attracted a lot of atention recently. Also, a proper choice of a Riemannian (or a Lipschitz-Riemann) structure seems to be a key step for efficient path-following on manifolds.

This talk is about Newton iteration on Riemannian manifolds. I will not consider the path-following problem here. Instead, I will make the case for the following table for covariant Newton iteration on manifolds.

Depends ? Newton Iteration alpha-theory
------------------------------------------------------------------------------
Riemannian metric Not really Yes.
Connection Yes No

Newton iteration can be defined independently of the Riemann structure, up to first order. However, all of alpha-theory 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 well-studied variations of Newton iteration do not fit into the Rie- mannian Newton framework. This is the case, for instance, of Gauss-Newton iteration in Interior Point Methods. We shall therefore extend alpha-theory 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 non-linear equation solving (Theorem 26 below contains the precise state- ment).

Thursday
October 8, 2009

2-3 pm
Stewart Library

Javier Pena (visiting Fields from CMU)
On the distance to ill-posedness
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
October 14, 2009
2-3 pm
Stewart Library

Jean Lasserre (visiting Fields from LAAS in France)
Approximate volume and integration for basic semi-algebraic sets

Thursday
October 15, 2009
2-3 pm
Stewart Library

Peter Scheiblechner
Castelnuovo-Mumford Regularity and Computing the de Rham Cohomology of Smooth Projective Varieties

Monday
October 19, 2009
2-3 pm
Stewart Library

Bernd Bank
Wavelet design via algorithmic real algebraic geometry

Wednesday
October 28, 2009
2-3 pm
Stewart Library

Ricky Pollack
Double Permutation Sequences and Arrangements of Planar Families of Convex Sets
We (re)introduce Double Permutation Sequences, which provide a combinatorial encoding of arrangements of convex sets in the plane. To clarify the origin of this idea, we also (re)introduce Permutation Sequences, which provide a combinatorial encoding of planar configurations of finite sets of points. We also recall the notion of a topological affine plane and several (some new) of its properties. In particular, that there is a universal topological affine plane P (i.e. any finite arrangement of pseudolines is isomorphic to some arrangement of finitely many lines of P).

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
October 29, 2009
2-3 pm
Stewart Library

Michael Todd
Linear convergence of modified Frank-Wolfe algorithms for ellipsoid optimization problems
November 4, 2009
2-3 pm
Stewart Library
Jim Renegar.
Optimization Over Hyperbolicity Cones
Linear programming, second-order programming and semidefinite programming are examples of optimization problems for which the underlying cones (the non-negative orthant, the Lorentz cone, the cone of positive semidefinite matrices) are so-called 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
2-3 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 coordinate-free 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
November 11,2009

2-3 pm
Stewart Library

Minh Ha Quang
Vector-valued 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 operator-valued positive definite kernels and their associated vector-valued 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 manifold-valued data.

Thursday
November 12, 2009

2-3 pm
Stewart Library

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 Gevrey-1/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
November 26, 2009

2-3 pm
Stewart Library

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
December 2, 2009

2-3 pm
Stewart Library

Teresa Krick
On the Arithmetic Nullstellensatz

This talk will present an on-going 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 non-zero 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
December 3, 2009

2-3 pm
Stewart Library

Pascal Koiran
Hitting set constructions and applications to arithmetic circuit lower bounds

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.

In this talk I will present a hitting set construction for a restricted class of arithmetic circuits, and the corresponding lower bound.
I will also explain that hitting set constructions for another restricted class of of arithmetic circuits would imply lower bounds against general arithmetic circuits (and as a result a lower bound for the permanent).

   



Back to top