Graduate Courses at UC Berkeley in the Spring Semester 1997



Here are three graduate courses of possible interest to some of you
which will be offered at UC Berkeley in the Spring Semester 1997:

-----------------------------------------------------------------------------

   CS 294-4:    ALGEBRAIC COMPLEXITY THEORY
   Instructor:  Amin Shokrollahi        (amin@icsi, ICSI, Room 611)
   Time:        Wednesdays and Fridays, 12:30pm-2:00pm
   Place:       505 Soda Hall

In the first part of the course we introduce and analyze asymptotically fast
algorithms for polynomial multiplication,  multiplication, inversion, and
composition of power series (algorithms of Sieveking, Kung, Brent, and
Brent-Kung), polynomial greatest common divisors (Knuth-Schoenhage algorithm),
evaluation and interpolation, multiple evaluation (Horowitz's algorithm),
and Meyer auf der Heide's results on fast point location in arrangements
of hyperplanes. Students will be encouraged to implement some of these
algorithms in a computer algebra system.
     In the second part of the course we study techniques for proving lower
bounds on the complexity of many of the above problems. After introducing our
models of computation, we will discuss techniques based on linear independece
arguments (Pan's Subsitution method), intersection theory (Strassen's Degree
Bound), and topology (Milnor-Thom, Ben-Or bound). Using these methods we will
show the optimality of most of the algorithms introduced in the first part,
within our models of computation.
The course will cover parts of the forthcoming book Algebraic Complexity
Theory by P.~Buergisser, M.~Clausen, M.A.~Shokrollahi, which will appear as
Volume 315 of Grundlehren der mathem.  Wissenschaften, Springer, end of 1996.

-----------------------------------------------------------------------------

 MATH 274:      ENUMERATIVE COMBINATORICS
 Instructor:    Lynne M. Butler         (lbutler@msri.org, MSRI 317, 643-6032)
 Time:          Tuesdays and Thursdays, 9:30--11 a.m.
 Place:         Evans 939
 Text:          Richard P. Stanley: "Enumerative Combinatorics"

Enumeration problems arise in all branches of pure mathematics and
theoretical computer science.  Both the theory necessary to understand
them and the techniques used to solve them are covered in this
course.  The course begins with methods of enumeration that include
generating functions and inclusion-exclusion.  It progresses to
the theory of partially ordered sets and their M\"obius functions.
It concludes with a careful treatment of rational generating
functions and their applications.
   The lectures and assignments focus on aspects of enumerative combinatorics
relevant to future researchers in number theory, finite group theory,
algebraic topology, algebraic geometry and analysis of algorithms. Connections
with geometric combinatorics and representation theory are elucidated during
visits to MSRI in February and April. Banquet-style homework permits each
student to tailor the course to her background and interests.

-----------------------------------------------------------------------------

   MATH 274:    COMPUTATIONAL ALGEBRAIC GEOMETRY
   Instructor:  Bernd Sturmfels         (bernd@math, Evans 701)
   Time:        Tuesdays and Thursdays, 12:30pm-2:00pm
   Place:       939 Evans Hall

In the first half of this course we cover material from the forthcoming book
"Using Algebraic Geometry"  by David Cox, John Little and Donal O'Shea.
This new book is a sequel to the familiar text  "Ideals, Varieties and
Algorithms" by the same authors, which is a prerequisite for this course.
I plan to cover the chapters on Solving Polynomial Equations, Resultants,
Computations in Local Rings, Resolutions, Toric Methods, and Splines.
    In the second half we will discuss original research papers and open
problems in computational algebraic geometry. Possible topics include
primary decomposition, degree bounds for Groebner bases, generic initial
ideals, normalization, the effective Nullstellensatz, trivialization
of vector bundles, enumerative geometry, multivariate residues, D-modules.