Graduation Year
2021
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Mohamed Omar
Reader 2
Nicholas Pippenger
Terms of Use & License Information
Abstract
One of the main goals of theoretical computer science is to prove limits on how efficiently certain Boolean functions can be computed. The study of the algebraic complexity of polynomials provides an indirect approach to exploring these questions, which may prove fruitful since much is known about polynomials already from the field of algebra. This paper explores current research in establishing lower bounds on invariant rings and polynomial families. It explains the construction of an invariant ring for whom a succinct encoding would imply that NP is in P/poly. It then states a theorem about the circuit complexity partial derivatives, and its implications for elementary symmetric function complexity, and proposes potential implications for other classes of functions.
Recommended Citation
LeMay, Matthew, "The Complexity of Symmetry" (2021). HMC Senior Theses. 246.
https://scholarship.claremont.edu/hmc_theses/246
