Algebraic Techniques in Geometry: The 10th Anniversary

Abstract:

For the past 10 years, combinatorial geometry (and to some extent, computational geometry too) has gone through a dramatic revolution, due to the infusion of techniques from algebraic geometry and algebra that have proven effective in solving a variety of hard problems that were thought to be unreachable with more traditional techniques. The new era has begun with two groundbreaking papers of Guth and Katz, in 2008 and 2010. Their second paper has (almost completely) solved the notoriously hard distinct distances problem of Erdős, open since 1946.

It is now high time to celebrate the decade of extensive achievements that have been made since 2008, and in this talk I will survey some of the progress that has been made, including a variety of problems on distinct and repeated distances and other configurations, on incidences between points and lines, curves, and surfaces in two, three, and higher dimensions, on polynomials vanishing on Cartesian products with applications, on cycle elimination for lines and triangles in three dimensions, on range searching with semialgebraic sets, and I will most certainly run out of time while doing so.

Polynomial Systems Arising from Discretizing Systems of Nonlinear Differential Equations

Abstract:

Discretization of many systems of nonlinear differential equations leads to sparse systems of polynomial equations. For a given system of differential equations, there are many different (but tightly related) polynomial systems, e.g., using increasing grid sizes (or different grids) in finite difference methods leads to different systems of polynomials.

In recent years, progress in the numerical solution of systems of differential equations has been made by applying a numerical-algebraic-geometry approach to the associated polynomial. For some types of problems, the new solution methods are significantly faster than previous methods.

In this talk, I will discuss the polynomial systems arising from discretization, the new methods, and some issues that have arisen in their use.

Thirty Years of Virtual Substitution - Foundations, Techniques, Applications

Abstract:

In 1988, Weispfenning proposed virtual substitution as a genuinely new quantifier elimination (QE) technique for the linear theory of the reals with ordering. About ten years later, he generalized the method to quadratic occurrences of quantified variables and laid the theoretical foundation for its generalization to arbitrary degree bounds. In comparison to cylindrical algebraic decomposition, virtual substitution is particularly interesting for problems with low degrees, few quantifier alternations, and comparatively many parameters.

From the very beginning, the theoretical development of virtual substitution was accompanied by systematic implementations in Redlog, which is integrated with the computer algebra system Reduce. Implementations focused on the quadratic case in combination with strong heuristics for coping with occurrences of higher degrees. Only recently, Kosta provided with his PhD thesis a systematic and coherent framework covering virtual substitution for arbitrary degree bounds and a corresponding generic implementation, which he instantiated up to degree 3.

The talk gives an overview of the theoretical framework of virtual substitution for regular QE and variants like extended QE, generic QE, or local QE. We address complexity, as well as other advantages and disadvantages compared to other methods. On the practical side, we discuss implementation techniques, perspectives for pushing the current generic implementation to higher degrees, and applications. Applications range from geometry proving in the 1990s via verification to systematic support for satisfiability modulo theory solving (SMT) and qualitative network analysis of biological networks.