RAA! The Randomized Algebraic Algorithms Seminar!

RAA: The Randomized Algebraic Algorithms Seminar

W: 17:00-18:00 (with exceptions to be announced), MILNER 313

Facilitator: Dr. J. Maurice Rojas
E-mail: rojas@math.tamu.edu
Web Page: http://www.math.tamu.edu/~rojas

Short Description

Announcements, Links, and Downloads

Biblilography
































Short Description
While randomization has been a central tool in computer science for decades, its importance in algebraic geometry has only been realized recently. This seminar aims to provide a gentle introduction to some basic notions in algorithmic algebraic geometry, with an eye toward randomization.

There are 3 main goals, which will likely occupy more than a single semester:

1. Understanding the connection between probability distributions, A-discriminants, and the expected behavior of roots of systems of polynomial equations.

2. Understanding the algorithmic implications of (1), with an eye toward Smale's 17th Problem. (The latter problem deals with solving systems of polynomial equations in polynomial time, on average, in a sense that is useful for numerical analysis.)

3. Developing the background necessary to understand recent work of Shiffman and Zelditch on random holomorphic sections of line bundles over Kahler manifolds. (Their theory includes the theory of random matrices as a very special case.)

We will also explore relevant number-theoretic topics along the way, such as the distribution of primes in arithmetic progression. The latter is actually intimately connected with polynomial system solving over the complex numbers. Needless to say, we will also define basic algorithmic notions (such as complexity classes) along the way.

The facilitator (Rojas) will begin with some introductory talks, giving many examples along the way. THIS SEMINAR IS INTENDED FOR GRADUATE STUDENTS, so questions (and contributed talks!) are most welcome.

NOTE: We will meet in Milner, which has outside doors that close around 5:00 pm. So please try to come early, or call Rojas' cell number (979) 220-4273, if you have trouble entering the building.

























Announcements, Links, and Downloads
  • 1. 9/5/07: Today's meeting focussed on the hardness of finite field feasibility in one variable. More precisely, we began with a discussion of FEAS_R (the feasibility problem over a general ring R) and a (brief!) overview of what is known about it's avatars FEAS_Z, FEAS_Q, FEAS_R, and FEAS_C. We then spent the rest of the time giving an informal definition of NP, and narrowed our focus from FEAS_{F_primes} (a variant of FEAS_{F_p} where you add log p to the input size) and its univariate restriction. We ended by stating the main theorem for that day: FEAS_{F_primes}(``univariate polynomials'') is nearly NP-hard. More precisely, FEAS_{F_primes}(``univariate polynomials'') in BPP implies that NP is in BPP.