Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
The Slice Rank Polynomial Method, Thomas C. Martinez
The Slice Rank Polynomial Method, Thomas C. Martinez
HMC Senior Theses
Suppose you wanted to bound the maximum size of a set in which every k-tuple of elements satisfied a specific condition. How would you go about this? Introduced in 2016 by Terence Tao, the slice rank polynomial method is a recently developed approach to solving problems in extremal combinatorics using linear algebraic tools. We provide the necessary background to understand this method, as well as some applications. Finally, we investigate a generalization of the slice rank, the partition rank introduced by Eric Naslund in 2020, along with various discussions on the intuition behind the slice rank polynomial method and …
Going Meta On The Minimum Circuit Size Problem: How Hard Is It To Show How Hard Showing Hardness Is?, Zoë Bell
Going Meta On The Minimum Circuit Size Problem: How Hard Is It To Show How Hard Showing Hardness Is?, Zoë Bell
HMC Senior Theses
The Minimum Circuit Size Problem (MCSP) is a problem with a long history in computational complexity theory which has recently experienced a resurgence in attention. MCSP takes as input the description of a Boolean function f as a truth table as well as a size parameter s, and outputs whether there is a circuit that computes f of size ≤ s. It is of great interest whether MCSP is NP-complete, but there have been shown to be many technical obstacles to proving that it is. Most of these results come in the following form: If MCSP is NP-complete …