CS229r : Arithmetic Circuits (Fall 2017)

General information

Instructor : Mrinal Kumar
Email : last name AT cmsa DOT fas DOT harvard DOT edu
Prereq : CS 121/124/125 and Mathematical Maturity
Time : Friday, 10 am-1 pm
Location : MD G125 (Tentative)
Office hours : Thursday, 10am-11am

Course description

Multivariate polynomials have a ubiquitous influence in many areas of computer science, including, but not limited to, algorithm design, coding theory, combinatorics and pseudorandomness. Arithmetic circuits are a natural computational model which provide a succinct way to represent multivariate polynomials. They can be thought of as algebraic analogs of Boolean circuits, with elementary boolean operations (AND, OR, NOT) being replaced by elementary arithmetic operations (+, *, -, /) of polynomials.

The goal of this course is to provide a biased introduction to this area and to try and get a sense of the power and limitations of arithmetic circuits as a computational model. We hope to see a combination of both classical and recent results in this area, including some upper bounds, lower bounds and questions about factoring and derandomization. A tentative list of topics we will cover can be found here.

Problem sets

Summary of Lectures