Mini Real Algebraic Geometry Conference, Purdue, Jan 24, 2020.
Time and Location
2.30- 5.30 PM, Math 731
- Ali Mohammad Nezhad (Purdue), 2.30-3.20 PM, Math 731.
Title: On the central path of semidefinite optimization: degree and worst-case convergence rate.
Abstract: Semidefinite optimization is the optimization of a linear objective function over the cone of positive semidefinite matrices intersected with an affine subspace. From an algorithmic point of view, primal-dual interior point methods have been comprehensively studied for an approximate optimal solution of semidefinite optimization problems. However, the worst-case convergence rate of the central path, which lies at the heart of primal-dual path-following interior point methods, is still unknown. In this talk, we address this question and derive an upper bound on the worst-case convergence rate of the central path using its univariate representation. Since the primal-dual interior point methods closely follow the central path, its worst-case convergence rate serves as a quantitative measure of hardness for numerically solving a semidefinite optimization problem.
- Negin Karisani (Purdue), 3.30-4.00 PM, Math 731.
Title: Efficient simplicial replacement of semi-algebraic sets and applications.
We describe a singly exponential algorithm for computing a simplicial complex which is $\ell$-equivalent
to a given semi-algebraic set (for any fixed $\ell$). As a result we are able to give singly exponential
compleity algorithm for computing any fixed dimensional persistent homology groups of filtrations
of semi-algebraic sets by the sublevel sets of a polynomial.
(Joint work with Saugata Basu).
- Andrei Gabrielov (Purdue), 4.00 -4.50 PM, Math 731.
Title: Surface singularities in R^4: first steps towards Lipschitz knot theory.
A link of an isolated singularity of a two-dimensional semialgebraic surface in $R^4$ is a knot (or a link) in $S^3$. Thus the ambient Lipschitz classification of surface singularities in $R^4$ can be interpreted as a bi-Lipschitz refinement of the topological classification of knots (or links) in $S^3$. We show that, given a knot $K$ in $S^3$, there are infinitely many distinct ambient Lipschitz equivalence classes of outer metric Lipschitz equivalent singularities in $R^4$ with the links topologically equivalent to $K$.
- Marie-Francoise Roy (Rennes), 5.00 - 5.30 PM, Math 731.
Title: "Virtual roots".
A univariate polynomial of degree d does not always have d real roots and this basic fact is at the origin of real algebraic geometry. The usual fix is to consider complex roots and then a polynomial of degree d has d roots (when counted with multiplicities). Virtual roots are a a more recent approach, due to Henri Lombardi : they are real numbers, generalizing the real roots, and a polynomial of degree d has d virtual roots counted with multiplicities. Virtual roots give a new perspective on ancient results by Descartes and Budan Fourier. They constitute the first step in the study of constructive real algebraic geometry for real real numbers, where the sign of a number cannot always be decided. There is also hope to use them to improve degree bounds in effective Hilbert 17 th problem.