CS 598 MAF

Subject offerings of new and developing areas of knowledge in computer science intended to augment the existing curriculum. See Class Schedule or departmental course information for topics and prerequisites. Course Information: May be repeated in the same or separate terms if topics vary.

The use of algebraic techniques (addition, multiplication, derivatives, and beyond) is pervasive in the design of efficient computation. This course will explore how these techniques apply to problems of an inherently algebraic nature, such as computing the determinant of a matrix, as well as for tasks that seemingly lack algebraic structure, such as combinatorial optimization. The course will develop the theory of using algebraic circuits to compute multivariate polynomials. This includes non-trivial algorithmic paradigms for efficient computation in this model (upper bounds), methods for proving that certain polynomials cannot be efficiently computed (lower bounds), as well as algorithms for efficiently deciding whether a given algebraic circuit computes the zero polynomial (polynomial identity testing). The course will also explore the underlying algebraic geometry of algebraic computation, especially in order to address foundational questions. This exploration will be with an ey