Spring 2007


 From the Director

 In this issue:

 Recent Programs

 Upcoming Programs

 Upcoming Opportunities



 Other issues

 IMA Home

Applications of Algebraic Geometry

The 2006–2007 thematic program on Applications of Algebraic Geometry is drawing to a close with our last workshop on Non-Linear Computational Geometry to be held from May 29 to June 2, 2007.

The Spring semester included two very superb tutorials Algebraic Algorithms in Optimization, and What is Algebraic Geometry?, both followed by two very successful workshops on Optimization and Control, and Complexity, Coding, and Communications. These programs were well attended and well received by the participants.

Here are two of reports from the organizers of the Optimization and Control workshop.
The winter workshop "Optimization and Control" of the IMA 2006-2007 program on "Algebraic Geometry and Its Applications" was very successful with respect to several criteria:

1. The audience: more than 120 people registered and the auditorium was almost packed at each session.

2. Most presentations were of high quality and addressed interesting issues that provide several avenues of research for the future.

3. The "last chance" sessions were also very lively and successful. In particular, one conclusion was that participants all agree on the need for new SDP solvers, which are more efficient in terms of numerical stability and capability for handling larger size problems. Another mentioned possibility is to develop specialized solvers to handle the specific algebraic features of the SDP relaxations associated with global optimization problems.

4. Interaction between participants: This workshop stimulated interaction between people in algebraic geometry (classical and real) on one side and people in optimization and control on the other side. It now becomes more and more apparent that both sides (and not only the optimization side) benefit from this interaction. Some papers already published and other submitted, support this claim. It is also clear same (or similar) techniques could be applied to other applications than control and optimization and compete with previously known methodologies. For example, the method of moments with its many applications could now benefit from the above methodology and remove some of its limitations.

5. The workshop nicely complements the other more computational oriented workshops of the 2006-2007 IMA program on algebraic geometry and its applications.

— Jean Bernard Lasserre

The workshop's main objective was to bring together several non-homogeneous groups of researchers interested in polynoial optimization, in its widest sense. The attendance was spectacular, with more than 120 registered participants, and the atmosphere was vibrant and enthusiastic. A real exchange of new ideas (and there were many) took place under the perfect ambiance offered by IMA and its wonderful staff. At this moment, the import of real algebra and real algebraic geometry to polynomial optimization is not new. However, this interdisciplinary venture (with methods of functional analysis added to it) has reached a maturity age. Well represented were the topics selected by the main speakers. Here are a few: optimization algorithms based on exact arithmetics; remarkable applications to discrete, combinatorila problems; a better understanding of the Linear Matrix Inequalities reductions and the Semidefinite Programming relaxations; a thorough study of the complexity of computations and optimization of sparse polynomials and sparse graphical models moment problems and duality techniques. The meeting will undoubtedly have a long term impact, by its novel scientific ideas and mostly by the new collaborations and direct contact established during its five day period. ,

— Mihai Putinar
The abstracts and talk materials for this workshop can be found on our web page.

In the words of some of the participants:
The workshop was excellent! I have met quite a few people here in person whom I communicated only be e-mail before or had no previous interactions at all. As a result of the workshop, I might follow up on a new idea regarding strict complementarity for the so-called second-order conic programming that came to me after the talk on the algebraic structure of the SDP cone and the related issue for positive semi-definite programming.
The workshop focused on the growing intersection of semi-definite programming, real algebraic geometry, and operator theory. As a result of the workshop I have a clearer understanding of the connections and important directions as well as a good list of new problems. I note that as a result of the activities related to the workshop major progress has been made on the Linear Matrix Inequality (LMI) lifting problem.
—Scott McCullough
I enjoyed the workshop very much. The time spacing allowed me to interact with many of the participants between talks. I made a number of new contacts both in my field and outside. I did prefer the days with 4 talks because the breaks on other days did seem a bit too long. Most of the talks were excellent as well, which is not always the case in interdisciplinary settings. I thought the office staff was stellar! I have no complaints. This was one of the best organized workshops that I have attended. I appreciate that all of the talks are on the web so that I can take more time to think about them later. This was also one of the most useful workshops that I have attended.
—Dennice Gayme

This is what the organizers of this workshop on Complexity, Coding, and Communications had to say:

Algebraic geometry is by now well known to have numerous applications in computational complexity and coding theory. The goal of this workshop was to bring together researchers from different sides of applications for presenting recent developments and for a fruitful exchange of ideas. The lectures covered a wide area of topics: quantitative and algorithmic questions of algebraic geometry, algebraic complexity theory, geometric invariant theory, and various aspects of coding theory. The speakers took great care in gently introducing their subjects to account for the different backgrounds in the audience and presented well prepared talks of high quality. There was a lot of interaction going on between the participants, as evidenced by the large number of questions asked during the talks and in the lively "second chances" sessions. The format of having only three talks per day allowed for ample discussions and a relaxed atmospere. The pure algebraic geometers in the audience were astonished to learn about the wide range of applications and the new type of questions coming from complexity question. It is to be hoped that the interaction between different fields will be stimulated by this event. I received very positive feedback from many participants confirming by own impression of the great success of this workshop.
—Peter Buergisser
Here is what some of the participants had to say:
This was a very good workshop, and I see the possibility of a new direction of research based on the connection between the computational complexity and the Schubert calculus that I learned at this workshop. I was working on the problems of complexity and on the geometry of Schubert varieties before, but never expected these two areas to be related. The IMA support was excellent. There was a small glitch with computer accounts at the start of the workshop, but that was fixed fast. During the workshop, there was enough time for communication with participants outside the lectures. In particular, I have made considerable progress in my work with Vorobjov on the topological complexity of semialgebraic sets and, more general, definable sets in an o-minimal structure. Our theorem settles a long-standing problem of a single exponential (in the number of variables) upper bound on the topological complexity of a projection of a fewnomial semialgebraic set. Our previous result provided such an upper bound only for a closed or open projection. Even in the classical (dense encoding) case of a general semialgebraic set our new construction often provides better upper bounds on the topological complexity than those known before.
—Andrei Gabrielov
I gained a better view of the current problems of interest in the fields of Complexity and Coding. I consolidated old contacts and met new people, mainly from the area of Coding Theory. I discussed some interesting questions with people I wouldn't have met without this workshop, that might lead to a project. The IMA staff is always very helpful and nice. The logistic was fine. The hotel is very convenient.
—Teresa Krick
The abstracts and talk materials for this workshop can be found on our web page.