Talks
Fall 2018

Lower Bounds in Arithmetic Circuit Complexity I

Wednesday, August 22nd, 2018, 2:00 pm3:00 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.