A Proof of Strassen's Degree Bound for Homogeneous Arithmetic Circuits

Abstract

The field of algebraic complexity theory is concerned with the amount of fundamental resources needed to perform various algebraic computations. One of the central challenges of algebraic complexity theory is to find explicit polynomials that cannot be computed by small arithmetic circuits. Strassen’s degree bound on the complexity of circuits computing various natural explicit collections of polynomials – such as (x_1)^k, (x_2)^k, ..., (x_n)^k, as well as the elementary symmetric polynomials – remains unsurpassed in this regard 45 years after its publication. In this thesis, I introduce arithmetic circuits and the degree bound, and I provide an alternate proof for the special class of arithmetic circuits known as homogeneous arithmetic circuits.