Fall 2018

Lower Bounds in Arithmetic Circuit Complexity II

Wednesday, August 22nd, 2018 3:30 pm4:30 pm

Add to Calendar

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.