Abstract

Arithmetic circuits are the natural computational model for problems that can be cast in the language of computing one or more multivariate polynomials. The Determinant, Permanent, and Matrix Multiplication are some well-known examples of problems of this kind. In this tutorial, we will start with basic definitions related to the arithmetic circuit model (and variants), introduce some basic questions regarding this model, and see the ideas behind some well-known lower bound results in the area.

Video Recording