Próxima Charla

Miércoles 20 de abril de 2011 - 15.40 hs

Michael Shub

Universidad de Buenos Aires

Complexity and Bezout's Theorem: Survey of Some Results and Some Open Problems

I will review some fundamental notions and recent progress by Beltran-Pardo and Buergisser Cucker on Smale's 17th problem. Can one find a root of a polynomial system approximately with average polynomial time and a uniform algorithm., as well as relations with complexity theory and some open problems.

Charlas anteriores

Miércoles 6 de abril de 2011 - 15.40 hs

Alicia Dickenstein

Universidad de Buenos Aires

Polynomials and mass action kinetics chemical reaction networks

This talk will be a gentle introduction to the systems of non linear ODE´s modeling mass action kinetics chemical reaction networks. These systems have interesting combinatorial, algebro-geometric and dynamical properties.

Miércoles 30 de marzo de 2011 - 15.40 hs

Teresa Krick

Universidad de Buenos Aires

On arithmetic effective Nullstellensätze and implicitation problems

Joint work with Carlos D'Andrea and Martin Sombra, on precise bounds for the effective Nullstellensatz and the implicitation problem in their arithmetic aspects.

The Nullstellensatz establishes that if f_1,...,f_s in k[x_1,...,x_n] are polynomials with no common roots in the algebraic closure of the field k, then they satisfy a Bezout identity 1=g_1f_1+...+g_sf_s for some polynomials g_1,...,g_s in k[x_1,...,x_n].

The implicitation problem consists in computing equations for an algebraic variety from a given rational parameterization of it. The typical case is when the variey is a hypersurface, in which case it is defined by a single ``implicit equation'' and the problem consists in computing it.

Miércoles 16 de marzo de 2011 - 15 hs

Pablo Heiber

Universidad de Buenos Aires

A better complexity of finite sequences

Joint work with Veronica Becher

We present a new complexity function defined from combinatorial properties of strings, and we prove that not only it satisfies fundamental properties of program-size complexity, but also it is computable in linear time and space. Our function is monotone in the prefix ordering of strings, and subadditive for concatenation. We prove an upper bound of the number of strings with complexity up to a given value, and we show that most strings of any given length have almost maximal complexity. No previously known efficiently computable functions meet all these basic properties of classical description complexity.

Description complexity, in each of its varieties, has been defined as minimal description length for a given description method.

In every case it is been hard, when even possible, to relate it with combinatorial properties of strings and, for computable versions, with string processing algorithms and data structures.

Our function uses an algebraic approach, which calculates complexity in terms of the set of substrings of the given string. This kind of definition is in the field of stringology, unlike description complexities.

This aims at narrowing the gap between the two views.

Miércoles 16 de marzo de 2011 - 15 hs

Gabriela Jerónimo

Universidad de Buenos Aires

A Geometric Approach to Differential Algebraic Equation Systems

One of the main invariants of a Differential Algebraic Equation (DAE) system is its differentiation index. There are several definitions of differentiation indices not all completely equivalent. Roughly speaking, for first order systems, the differentiation index counts the number of total derivatives of the system needed to obtain an explicit ODE.

From the point of view of numerical solving, it is desirable for a DAE to have a differentiation index as small as possible. This motivates the study of index reduction methods, which given a DAE system compute a new system, in some sense equivalent to the input DAE, but with a lower differentiation index (possibly 0 or 1).

We will present an algebraic definition of a differentiation index for a wide class of DAE systems and address the index reduction problem for these systems. We will show that any of these systems can be transformed into a generically equivalent first order DAE system consisting of a single purely algebraic (polynomial) equation plus an under-determined ODE (that is, a semi-explicit DAE system with differentiation index 1). Finally, we will describe an algorithm with bounded complexity which computes this associated system.

This is a joint work with Lisi D'Alfonso, François Ollivier, Alexandre Sedoglavic and Pablo Solernó.

Miércoles 30 de febrero de 2011 - 15 hs

Guillermo Matera

Lower bounds for robust interpolation algorithms

In this lecture we shall discuss lower bounds on the complexity of robust algorithms for solving families of interpolation problems. Our notion of robustness models the behavior of all known universal methods for solving families of interpolation problems avoiding unnecessary branchings and allowing the solution of certain limit problems. We shall first show that a robust algorithm solving a family of Lagrange interpolation problems with N nodes encoded by a Zariski open subset of the N-dimensional complex space has a cost which is at least linear in N, showing thus that standard interpolation methods are essentially optimal. Then we shall consider families of interpolation problems with singularities. In particular, we shall consider the family of problems which consists of interpolating a polynomial given by a straight-line program of length L from its value in a correct-test sequence. We shall show that any robust algorithm solving such a family of problems requires a number of arithmetic operations which is exponential in L. Joint work with Nardo Gimenez, Joos Heintz and Pablo Solerno.

Miércoles 23 de febrero de 2011 - 15 hs

Joos Heintz

Departamento de Computación, Universidad de Buenos Aires

The Software Architecture of Algebraic Geometry

In 1978 Malte Sieveking (Goethe-Universität, Frankfurt) and myself introduced the arithmetic circuit representation of polynomials in effective algebraic geometry and asked for a non-polynomial lower complexity bound for the elimination of a single existential quantifier block in circuit represented formulas of the first order theory of algebraically closed fields. For this purpose I showed together with Claus Peter Schnorr (Goethe-Universität, Frankfurt) that identity of circuit represented polynomials can efficiently be checked. In this context, we arrived at a couple of basic questions like the determination of the complexity character of the gcd of two circuit represented polynomials (without the trivializing reference to their degree of course). This and other related problems remain today completely unsolved.

The question of the complexity status of quantifier elimination over algebraically closed fields was later reformulated and reconsidered in the context of the BSS model. In the last twelve years I started with my collaborators (Pablo Solerno, Guillermo Matera and others) to reanalyze the problem of the lower complexity bounds for quantifier elimination in circuit represented first order formulas of the first order theory of algebraically closed fields.

The goal was to show the optimality of the pseudpolynomial "Kronecker" algorithm for the solution of multivariate polynomial equation systems, which became developed and implemented in the last 10-15 years by the international peronist research group TERA. The basic idea, which during the last seven years slowly took form, was to restrict the algorithmic model by means of well motivated architectural quality requirements. This was finally achieved thanks to the development of a refinement of the theory of rational maps in algebraic geometry. The basic outcome of this refinement is the notion of a geometrically robust constructible map. The motivation is given as a nontrivial application of Zariski's Main Theorem to Computer Science.

These lectures contain joint work with Andrés Rojas Paredes.We elaborated together an architecture based computation model which allows to express all known symbolic and seminumeric computational methods in effective algebraic geometry. The particular properties of this model are implications of well motivated and natural quality requirements on the procedures of this model. These procedures transform so called robust parametrized arithmetic circuits in other ones. The main tool for establishing the model are the geometrically robust constructible maps. Within our computation model we are able to give a mathematical proof of the intrinsic exponential complexity character of already most simple elimination problems in effective algebraic geometry.

The mathematical aspect of this proof is also interesting. The argument is based on the exhibition of a computationally well motivated rational map such that any factorization of this map by simple blow ups and a polynomial map requires an exponential number of them. Such a type of statement was not known before in singularity theory.

All these methods may also be applied to other fields of Scientific Computing, for example to polynomial interpolation. One may show that coalescent (i.e., geometrically robust) interpolation of circuit represented multivariate polynomials requires exponential time (joint work with Nardo Giménez, Guillermo Matera and Pablo Solerno).

Para más información, contactar a Michael Shub ( michael.shub@gmail.com ).