Skip navigation
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorDvir, Zeev-
dc.contributor.advisorRaz, Ran-
dc.contributor.authorEdelman, Benjamin-
dc.description.abstractThe 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.en_US
dc.titleA Proof of Strassen's Degree Bound for Homogeneous Arithmetic Circuitsen_US
dc.typePrinceton University Senior Theses-
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
EDELMAN-BENJAMIN-THESIS.pdf198.14 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.