Course MAT576

Advanced Topics in Computer Science: Arithmetic circuits

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 has 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 nontrivial 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.

Placement and Prerequisites

Recommended background: Previous exposure to basic notions in Algebra such as fields, vector spaces, dimension, polynomials and groups.

Computer science background is not necessary.