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 abstracts and talk materials for this workshop can be found on our web page.
In the words of some of the participants:
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 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
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
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)
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.
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.
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
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.
The abstracts and talk materials for this workshop can be found on our web page.