Algebraic Complexity Seminar

More Basic Notions in Arithmetic Complexity

In this lecture we are going to give basic definitions of arithmetic circuits, and define notions such as the size and depth of a circuit, as well as the corresponding notion for formulas. We then define the complexity classes VP (the class of polynomials with small circuits) and VNP (the class of explicit polynomials). We then discuss the notion of a (computational) reduction from one polynomial to another, and use this notion to define the phenomenon of `completeness', that is, the existence of polynomials that capture (via reductions) the complexity of classes such as VP and VNP.  With this idea in mind, we can then show that every polynomial computed by a small formula efficiently reduces to the determinant.  If time allows, we will then discuss structural results showing how one can convert arbitrary computation into certain normal forms, such as homogeneous computation or low-depth computation.