Please use this identifier to cite or link to this item:
|Title:||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.|
|Type of Material:||Princeton University Senior Theses|
|Appears in Collections:||Mathematics, 1934-2020|
Files in This Item:
|EDELMAN-BENJAMIN-THESIS.pdf||198.14 kB||Adobe PDF||Request a copy|
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.