Master’s Thesis Presentation • Symbolic Computation | Computer Algebra — Analysis of Randomized Algorithms in Real Algebraic Geometry

Please note: This master’s thesis presentation will be given online.

Jesse Elliott, Master’s candidate
David R. Cheriton School of Computer Science

Consider the problem of computing at least one point in each connected component of a smooth real algebraic set. This is a basic and important operation in semi-algebraic geometry. It gives an upper bound on the number of connected components of the algebraic set, it can be used to decide whether or not the algebraic set has real solutions, and it is also used as a subroutine in many higher level algorithms.

We consider an algorithm for this problem by Safey El Din and Schost: “Polar varieties and computation of one point in each connected component of a smooth real algebraic set” (ISSAC’03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model, and the analysis of the bit complexity and the error probability were left for future work.

We also consider another algorithm that solves a special case of the problem. Namely, when the algebraic set is a compact hypersurface.

We determine the bit complexity and error probability of these algorithms. Our main contribution is a quantitative analysis of several genericity statements, such as Thom’s weak transversality theorem and Noether normalization properties for polar varieties. Furthermore, in doing this work, we have developed techniques that can be used in the analysis of further randomized algorithms in real algebraic geometry, which rely on related genericity properties.

To join this master’s presentation on Zoom, please go to https://us02web.zoom.us/j/85446398177?pwd=TjJVU1BJN3Iwc05IS3N1bUtrVFFyZz09.

Meeting ID: 854 4639 8177 
Passcode: 199196