THEMATIC PROGRAMS

March 19, 2024

Thematic Program on the Foundations of Computational Mathematics July-December, 2009

October 20 - 24, 2009 (Tues.-Sat.)
Workshop on Complexity of Numerical Computation

Organizing Committee:
Teresa Krick (University of Buenos Aires)- Chair
Felipe Cucker (City University of Hong Kong)
Askold Khovanskii (University of Toronto)
Adrian Lewis (Cornell University)
Michael Shub (University of Toronto)

Mailing List : To receive updates on the program please subscribe to our mailing list at www.fields.utoronto.ca/maillist

Complexity issues lie at the core of the theory of computation. The size of many practical problems demands the study of their intrinsic complexity and the efficiency of any proposed algorithms. Theoretical results have often resulted in real practical improvements in computation, such as that of Khachiyan who showed the polynomial-time solvability of linear programming in 1979 -- although the resulting "ellipsoid algorithm" was not practically competitive with the simplex method, it nevertheless led to modern interior-point algorithms which can outperform simplex algorithm on many large linear programs.

This workshop will involve three major subareas of complexity:

  • Complexity of Algebraic Geometry-- the complexity of solving polynomial systems.
  • Emerging themes in optimization--the above-mentioned ellipsoid algorithm shows the importance of fundamental results for practical applications.
  • Algebraic and semi-algebraic Complexity--this area provides a uniform foundation for the first two.

There will be 5 short courses of 3 or 2 lectures each in these major areas, and a dozen talks of 45 minutes plus questions. We expect to leave enough free time to the participants to favour interaction and discussions.

We will also take the opportunity to celebrate Jean Pierre Dedieu's 60th birthday during a conference dinner in his honor, which will be preceded by a talk describing his major contributions to the field.

 

Invited Speakers

Saugata Basu (Purdue University)
Carlos Beltrán (Universidad de Cantabria)
Peter Bürgisser (Universität Paderborn)
Felipe Cucker (City University of Hong Kong)
Alexandre D'Aspremont (Princeton University)
Jean Pierre Dedieu (Universite de Toulouse)
Marc Giusti (Ecole Polytechnique Palaiseau)
Bill Helton (UC San Diego)
Askold Khovanskii (University of Toronto)

Gregoire Lecerf (Université de Versailles)
Renato Monteiro (Georgia Institute of Technology)
Bernard Mourrain (INRIA Sophia Antipolis)
Marie-Francoise Roy (Universite de Rennes 1)
Andrew Sommese (University of Notre Dame)
*Paul Tseng (Washington University)
Joris van der Hoeven (Université Paris-Sud)
Yinyu Ye (Stanford University)

Tentative Workshop Schedule revised October 20

Tuesday October 20
9:00-10:00 Coffee
10:00-10:10 Welcome and Introduction
Workshop Organizers
10:10-11:00 Lecture 1
Peter Bürgisser (Universität Paderborn)
Felipe Cucker (City University of Hong Kong)
Condition
11:10-12:00 Lecture 1
Jean Pierre Dedieu (Universite de Toulouse)
Complexity of Bezout's Theorem and the Condition Number
12:00-2:10 Lunch
2:10-3:00 Lecture 1
Gregoire Lecerf (Université de Versailles)
Symbolic deformation techniques for polynomial system solving
3:00-3:30 Tea
3:30-4:20 Lecture 1
Askold Khovanskii (University of Toronto)
An interplay between Algebraic Geometry and Convex Geometry
4:30-5:20 Marie-Francoise Roy (Universite de Rennes 1)
Certificates of positivity in the Bernstein basis
5:30-6:20 Reception
Fields Institute Atrium
Wednesday October 21
9:00-9:50 Lecture 2
Jean Pierre Dedieu (Universite de Toulouse)
Complexity of Bezout's Theorem and the Condition Number
9:50-10:10 Coffee
10:10-11:00 Lecture 2
Gregoire Lecerf (Université de Versailles)
Symbolic deformation techniques for polynomial system solving
11:10-12:00 Andrew Sommese (University of Notre Dame)
Zebra Fish, Tumor Growth, and Algebraic Geometry
12:00-2:10 Lunch
2:10-3:00 Lecture 1
Renato Monteiro (Georgia Institute of Technology)
Algorithms for large scale structured optimization problems
3:00-3:30 Tea
3:30-4:20 Alexandre D'Aspremont (Princeton University)
Tractable performance bounds for compressed sensing
4:20- 5:10 Joris van der Hoeven (Université Paris-Sud)
On the art of guessing
Thursday October 22
9:00-9:50 Lecture 2
Peter Bürgisser (Universität Paderborn)
Felipe Cucker (City University of Hong Kong)
Condition
9:50-10:10 Coffee
10:10-11:00 Lecture 2
Askold Khovanskii (University of Toronto)

An interplay between Algebraic Geometry and Convex Geometry
11:10-12:00 Marc Giusti (Ecole Polytechnique Palaiseau)
On the geometry of polar varieties
12:00-2:10 Lunch
2:10-3:00 Myong-Hi Kim (SUNY at Old Westbury)
The average cost of one variable root finding polynomial
3:00-3:30 Tea
3:30-4:20 Lecture 2
Renato Monteiro (Georgia Institute of Technology)
Algorithms for large scale structured optimization problems
4:30-5:20 Free time
5:30-6:20 Luis Miguel Pardo (Universidad de Cantabria)
On the work of Jean-Pierre Dedieu
7:00 Workshop dinner for Dedieu
93 Harbord St.
Friday October 23
9:50-10:10 Coffee
10:10-11:00 Lecture 3
Jean Pierre Dedieu (Universite de Toulouse)
Complexity of Bezout's Theorem and the Condition Number
11:10-12:00 Lecture 3
Peter Bürgisser (Universität Paderborn)
Felipe Cucker (City University of Hong Kong)
Condition
12:00-2:10 Lunch
2:10-3:00 Yinyu Ye (Stanford University)
On the complexity of L-p norm minimization for p less than 1
3:00-3:30 Tea
3:30-4:20 Saugata Basu (Purdue University)
Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem
4:30-5:20 Carlos Beltrán (Universidad de Cantabria)
Path-following methods for solving Smale's 17th problem. Recent progress and open questions
Saturday October 24
9:30-10:20 Lecture 3
Renato Monteiro (Georgia Institute of Technology)
Algorithms for large scale structured optimization problems
10:20-10:40 Coffee
10:40-11:30 Bernard Mourrain (INRIA Sophia Antipolis)
Isolation of real roots of polynomial systems, complexity and condition number
11:40-12:30 Lecture 3
Gregoire Lecerf (Université de Versailles)
Symbolic deformation techniques for polynomial system solving


Confirmed Participants as of November 3, 2009

Full Name University/Affiliation
Amelunxen, Dennis Universität Paderborn
Andrews, Rob (no affiliation)
Armentano, Diego Universidad de la República
Bank, Bernd Humboldt--Universitaet zu Berlin
Basu, Saugata Purdue University
Beltrán, Carlos Universidad de Cantabria
Berz, Martin Michigan State University
Blum, Lenore Carnegie Mellon University
Boito, Paola Emory University
Briquel, Irénée Ecole Normale Supérieure de Lyon
Bürgisser, Peter Universität Paderborn
Cheng, Qi University of Oklahoma
Cheung, Kevin Carleton University
Chèze, Guillaume Institut de Mathématiques de Toulouse
Conidis, Chris University of Waterloo
Coons, Michael J. Simon Fraser University
Cucker, Felipe City University of Hong Kong
D’Andrea, Carlos Universitat de Barcelona
d'Aspremont, Alexandre Princeton University
Dedieu, Jean-Pierre Université de Toulouse
Di Fiore, Carlos University of Buenos Aires
Di Rocco, Sandra KTH
Franklin, Johanna National University of Singapore
Ghaddar, Bissan University of Waterloo
Giusti, Marc CNRS-Polytechnique
Grenet, Bruno Ecole Normale Supérieure de Lyon
Grigo, Alexander Georgia Institute of Technology
Hammerlindl, Andy The Fields Institute
Hauenstein, Jonathan University of Notre Dame
Jeronimo, Gabriela Universidad de Buenos Aires
Khovanskii, Askold University of Toronto
Kim, Myong-Hi Nina SUNY College at Old Westbury
Koiran, Pascal ENS Lyon
Krick, Teresa Universidad de Buenos Aires
Laplagne, Santiago University of Buenos Aires
Lasserre, Jean Bernard LAS-CNRS
Lebreton, Romain Ecole Polytechnique
Lecerf, Grégoire Université de Versailles
Lewis, Adrian Cornell University
Leykin, Anton University of Illinois at Chicago
Li, Tien-Yien Michigan State University
Malajovich, Gregorio Universidade Federal do Rio de Janeiro
Martens, Marco SUNY at Stony Brook
Monteiro, Renato Georgia Institute of Technology
Mourrain, Bernard INRIA
Nabutovsky, Alexander University of Toronto
Naoum-Sawaya, Joe University of Waterloo
Nobakhtian, Soghra University of Isfahan
Pang, Chin How Jeffrey Cornell University
Pardo, Luis Universidad de Cantabria
Peña, Javier Carnegie Mellon University
Pong, Ting Kei University of Washington
Portier, Natacha ENS Lyon
Renegar, James Cornell University
Rojas, Cristóbal IML
Roshchina, Vera Universidade de Evora
Roy, Marie-Francoise Université de Rennes I
Scheiblechner, Peter Purdue University
Sethuraman, Swaminathan Fields Institute
Shub, Michael University of Toronto
Sommese, Andrew University of Notre Dame
Szanto, Agnes North Carolina State University
Todd, Michael J. Cornell University
Valdettaro, Marcelo University of Buenos Aires
van der Hoeven, Joris Université Paris-Sud
Vera, Juan University of Waterloo
Von zur Gathen, Joachim University of Bonn
Wampler, Charles General Motors R&D
Yampolsky, Michael University of Toronto
Ye, Yinyu Stanford University
Yomdin, Yosef The Weizmann Institute of Science

 

*Paul Tseng has been missing since taking a solo kayak trip in China in mid August. Our thoughts are with his family and his many friends.


Apply to the Program:
All scientific events are open to the mathematical sciences community. Visitors who are interested in office space or funding are requested to apply by filling out the application form. Additional support is available (pending NSF funding) to support junior US visitors to this program. Fields scientific programs are devoted to research in the mathematical sciences, and enhanced graduate and post-doctoral training opportunities. Part of the mandate of the Institute is to broaden and enlarge the community, and to encourage the participation of women and members of visible minority groups in our scientific programs.

For additional information contact thematic(PUT_AT_SIGN_HERE)fields.utoronto.ca

Back to Top