Computer Algebra in Scientific Computing

Invited Talks

We are proud to present exceptional researchers who will give invited talks at CASC conference:

Families of polynomials in the study of biochemical reaction networks

Alicia Dickenstein

I will motivate and describe several algebro-geometric computational techniques used for the study of families of polynomials that arise in the realm of biochemical reaction networks, as well as some mathematical challenges that we face.

Distance Geometry and the m-Bezout bound

Ioannis Emiris

Distance geometry studies structures with a finite number of configurations, up to rigid transformations, which are prescribed by the distances between a set of points. Equivalently, one may think of weighted graphs whose vertices admit a finite number of embeddings so as to respect the given edge lengths. A fundamental problem in distance geometry is to enumerate these embeddings in euclidean space.

Typically, one constructs an algebraic system whose solutions correspond to the different embeddings. This talk surveys methods for modeling the problem effectively, but also for bounding the corresponding root count by means of algebraic geometry. Surprisingly, the best asymptotic bound had been Bezout's applied to the obvious system of quadratic equations expressing the length constraints. This bound is exponential in n, with base 2d for graphs of n vertices in d dimensions. This implies a base of 4 for the most famous case of Laman graphs in the plane. Moreover, the best lower bound has a base of 2.5.

We propose a new method that introduces a combinatorial process in terms of directed graphs with constrained orientations and manages to improve the existing bounds in all dimensions. In particular, for Laman graphs our exponent's base is inferior to 3.8. Algebraically, we rely on the m-Bezout bound of multihomogeneous systems. The latter is computationally #P-hard by reduction to the permanent. We derive a closed formula of a bound on the m-Bezout number of sparse multihomogeneous systems whose equations include two variable subsets. Our bound is tighter than bounds on the permanent.

Τhis is joint work with E. Bartzos, J. Schicho, and R. Vidunas.