20/05/2009, 14:30 — 15:30 — Sala P3.10, Pavilhão de Matemática J. Maurice Rojas, Texas A&M University
Number Theory, Randomization, and Real Topology Computation
Computing the topology of a real algebraic set given as the zero set of a list of polynomials remains a challenging problem, even for polynomials in 3 variables. Nevertheless, we can show that for certain systems of sparse polynomials, one can efficiently compute the topology in polynomial-time with high probability. This is recent joint work with Martin Avendano. We illustrate the algorithm through various examples, and see how a special case leads to the use of Diophantine approximation. We then show how, in more general cases, it is natural to expect a set of small set of inputs where the algorithm slows down. We assume no background in number theory or algorithms.
