This thin but dense volume emerged from a 2006 workshop of the same title, a workshop that drew 110 participants. The reader who has never heard of fewnomials, cohomology rings, the Zariski topology, or a Schubert variety will have difficulty penetrating the papers. Here, I will attempt to give a sense of two of the eight papers in the book.
“Efficient Inversion of Rational Maps Over Finite Fields” addresses a technical question inspired by cryptography. Some public-key encryption schemes effectively map an n-dimensional point in a finite field via a rational map, relying on the fact that solving equations over a finite field is nondeterministic polynomial time (NP) complete. However, several of the proposed schemes have proven to be insecure, suggesting that perhaps the maps used in encryption are special. This paper shows that inverting such a map, which is what it takes to crack the encoding, can be accomplished in exponential time in various geometric parameters of the map. There is evidence that this exponential dependence is necessary, and the result suggests that these schemes are likely secure.
“Semidefinite Representation of the k-Ellipse” proves several theorems about the k-ellipse, the plane curve that is the locus of all points whose sum of distances from k given foci is some prescribed number d. They compute and study the irreducible polynomial p(x,y) that vanishes on the k-ellipse, and prove that it has degree at most 2k if k is odd, and somewhat less if k is even. The k-ellipse itself is a convex curve (classically known as an Eikurven--an egg curve), but the Zariski closure p(x,y)=0 has many more branches. They show an example of this closure for a 5-ellipse, a beautifully intricate algebraic curve of degree 25=32. The point that realizes the smallest d is known as the Fermat-Weber point of the k foci and is of considerable interest for facility location.
The other six papers similarly have some connection to a motivating application, but the focus of all papers in this volume is on the deep technical algebraic geometry behind the algorithms.
