PhD Seminar • Symbolic Computation • On the Bit Complexity of Some Randomized Algorithms in Real Algebraic Geometry

Please note: This PhD seminar will take place in DC 2310 and online.

Jesse Elliott, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors David Jao, Éric Schost

We analyze the bit complexity of an algorithm for the computation of at least one point in each connected component of a smooth real algebraic set. This work is a continuation of our analysis of the hypersurface case (On the bit complexity of finding points in connected components of a smooth real hypersurface, ISSAC’20). Here, we extend the analysis to more general cases. Our starting point is an algorithm 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), which 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. Here, we analyze the bit complexity and the error probability, and we provide a quantitative analysis of the genericity statements. Furthermore, we use Lagrange systems to describe polar varieties because they provide a simpler framework for techniques such as weak transversality and an effective Nullstellensatz.

The techniques we develop apply generally to algorithms in real algebraic geometry where transversality or Noether position are required geometric properties established by a random change of coordinates. In work that is currently ongoing, we are reusing the techniques in the analysis of another algorithm by Safey El Din and Schost (A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, Discrete and Computational Geometry, 2011); this algorithm decides connectivity queries on smooth and bounded real hypersurfaces. In the presentation, I will also discuss our analysis of this algorithm.

To attend this PhD seminar in person, please go to DC 2310. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/3391868751.