Symbolic Computation Group

One reasonable measure of the size of the output of an algorithm which solves a zero-dimensional polynomial system is simply the number of solutions to the input system, otherwise known as the degree of the variety it defines. This measure, however, ignores the number of bits required to encode each solution. The (naïve, logarithmic) height of a variety is a finer-grained measure of its complexity, which, in the zero-dimensional case, captures the bit-sizes of its points. In this talk, I will discuss how sharp bounds on heights of determinantal varieties arise from new constructions in arithmetic integral geometry. Along the way, I will introduce a new perspective on the "determinantal resultant" which is a hypersurface whose degree and height closely mimics that of the determinantal variety from which it is constructed. This talk is based on joint work with Éric Schost, Mohab Safey El Din, and Vincent Neiger.