COS 597A / MAT 576
· If you are taking this course or want to get announcements about upcoming lectures please join the mailing list (you need to do this even if you are a registered student).
Professor: Zeev Dvir (follow link for contact information)
Office Hours: By appointment.
One the fundamental goals in computational complexity is to understand which functions are easy and which are hard to compute. This course will focus on this question from an algebraic perspective by studying the complexity of computing polynomials over a field using basic arithmetic operations. The basic model of computation is an arithmetic circuit, which is a circuit that takes variables and field constants as inputs and, at each gate, computes a sum or product of previously computed polynomials. Understanding the complexity of even the simplest polynomials in this model is a challenging (and mostly open) problem. However, a rich theory have evolved around this question and there are many beautiful and highly non trivial results known.
A partial list of topics includes: A sample of some non trivial arithmetic circuits for problems such as matrix multiplication, Fourier transform, polynomial evaluation etc. Structural results for circuits (homogenization, depth reduction, elimination of division gates). Lower bounds for circuits, formulas and for restricted models. Valiant's complexity classes VP and VNP and the algebraic version of the P vs. NP problem. Approaches for proving lower bounds (matrix rigidity, elusive mappings, tensor rank). Polynomial identity testing.
Recommended background: Previous exposure to basic notions in Algebra such as: fields, vector spaces, dimension, polynomials and groups. Computer science background is not necessary.
Grading: Problem sets.