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.