Geometry Seminar

Date: October 28, 2016

Time: 4:00PM - 5:00PM

Location: BLOC 628

Speaker: Maurice Rojas, TAMU

Title: How Quickly Can we Find the Shapes of Algebraic Sets? Part 2: Computing Topology over R

Abstract: In this series of lectures, we review some old and new results on computing the topology of algebraic sets. We work mainly over the fields C, R, and F_p. These lectures are meant to be accessible to first year graduate students. We consider the complexity of computing the number of connected components of the real zero set of a single sparse polynomial. Whereas the first part of Hilbert's 16th Problem asks for the disposition of the ovals of a plane curve of degree d, we instead consider the analogous problem for n-variate polynomials (of arbitrary degree) having n+k monomial terms. We'll see an efficient classification valid for k<=2. We then see why we get NP-hardness for k on the order of n^epsilon.