Workshop on Real Number Complexity

Foundations of Computational Mathematics.

Santander, 30th of June to 9 of July, 2005

General information

Worshop date and time: July 7-9, 2005, from 13:50 to 18:40

Location: Escuela Tecnica Superior de Ingenieros Industriales y Telecomunicaciones (ETSIIT), Universidad de Cantabria.

Local Information and maps

Organizers Peter Bürgisser, Paderborn.

Gregorio Malajovich, UFRJ.

Related links FoCM'2005 main page

FoCM main page

Abstracts Please see below.yy

Workshop description and scope

This workshop will focus on the complexity of equation solving (linear algebra problems, non-linear equations, path-following algorithms, etc...), and related models of computation (boolean, algebraic, real machines, decision trees, circuits, Valiant's model...).

As in the previous FoCM conference, Computational Algebraic Geometry will be covered by another workshop. (click here).

Talks will be 20 or 45 minutes long. We will give priority to participants that are not speaking in another workshop.

We still may have a few spots open, so feel free to contact the organizers,

List of participants.

Real Number Complexity: Schedule and Abstracts

Last updated on July 5th
TimeSpeaker Title and Abstract
Thursday, July 7th, 2005
13:50-14:35Victor Pan, Lehman College, City University of New York Polynomial root-finding with matrix eigen-solving
14:40-15:05Jean-Pierre Dedieu, Laboratoire MIP, Université Paul Sabatier-Toulouse A Gauss-Newton method for low-rank best approximation of a matrix
15:05-15:30J. Maurice Rojas, Department of Mathematics, Texas A&M University Parallels between Real and p-adic Complexity
15:30-16:00Coffee break
16:00-16:25Jose Luiz Montaña Arnaiz, Universidad de Cantabria On the number of random digits required in the MonteCarlo integration of definable functions
16:25-16:50Mark Braverman,Dept. of Computer Science,University of TorontoOn efficient computation of parabolic Julia sets
16:50-17:40Gregorio Malajovich(Semi-plenary talk), Departamento de Matemática Aplicada, Universidade Federal do Rio de Janeiro. On the Curvature of the Central Path of Linear Programming Theory
Friday, July 8th, 2005
13:50-14:15Peter Bürgisser, Department of Mathematics and Computer Science, University of Paderborn. Counting Complexity and Euler Characteristic of Semialgebraic Sets
14:15-14:40Saugata Basu, School of Mathematics, Georgia TechEfficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets.
14:40-15:05Klaus Meer, IMADA, University of Southern Denmark Probabilistically checkable proofs over the reals
15:05-15:30Lenore Blum, Department of Computer Science, Carnegie Mellon University Computing over the Reals: Where Turing meets Newton REDUX
15:30-16:00Coffee break
16:00-16:25Mario Wschebor, Centro de Matemática, Facultad de Ciencias de la Universidad de la República. Random systems of equations and the Rice formulai
16:25-16:50Guillaume Malod,Department of Information Science,Kyoto UniversityA uniform version of Valiant's algebraic complexity classes
16:50-17:40Pascal Koiran, LIP, École Normale Supérieure de Lyon. Some connections between the Blum-Shub-Smale and generalizations of Valiant's model.
17:40-18:30Felipe Cucker (Semi-Plenary talk), Department of Mathematics, City University of Hong Kong. Exotic quantifiers, complexity classes, and complete problems
Saturday, July 9th, 2005
13:50-14:40Jan Verschelde(Semi-Plenary talk), Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago. Software for Symbolic-Numeric Solutions of Polynomial Systems
14:40-15:30Yosef Yomdin, Department of Mathematics, Weizmann Institute Analytic reparametrizaton of algebraic sets as a tool for their computer modelling
15:30-16:00Coffee break
16:00-16:25Guillermo Matera,Instituto de Desarrollo Humano,Universidad Nacional de General SarmientoOn the approximation of the stationary solutions of certain semilinear parabolic PDEs
16:25-16:50Jean-Claude Yakoubsohn, Laboratoire MIP, Université Paul Sabatier-Toulouse Kantorovitch analysis for multiple zeros of univariate analytic functions
16:50-17:40Jean-Marie Morvan (to confirm), Université de Lyon TBA
17:40-18:30Open problems session, organizational meeting, etc...

Related sites.

FoCM Main Homepage
Foundations of Computational Mathematics - the Journal