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