Fields Institute - Thematic Program on Mathematics in Quantum Information

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).