# 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.

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: