Campuses:

On the effectiveness of number theory in algebraic geometry

Wednesday, September 20, 2006 - 10:50am - 11:40am
EE/CS 3-180
J. Maurice Rojas (Texas A & M University)
One of the most basic notions in polynomial system
solving
is feasibility: does your system of equations have any roots?
We will
explore the algorithmic complexity of this problem, focussing
on
sparse polynomial systems over the real numbers and complex
numbers.

Over the complex numbers, we will see algorithms
completely
different from homotopy, resultants, and Grobner bases; and how
the
Generalized Riemann Hypothesis enters our setting. In
particular, we
show how earlier methods (of Grigoriev, Karpinski, Odlyzko, and
Koiran),
depending on unproven number-theoretic hypotheses, can be made
unconditional in certain cases.

Over the real numbers, we will determine the threshold
between
polynomial-time and NP-hardness, as a function of the number of
variables and monomial terms. In particular, we will give
polynomial-time algorithms where
only exponential-time algorithms were known before, and we will
see how
Diophantine approximation enters in an unexpected way.

Along the way, we will see how finite fields and p-adic
fields are also related to our main focus.
MSC Code: 
11-XX
Keywords: