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.