Skip navigation
Please use this identifier to cite or link to this item:
Title: Energy Function Arguments in Finding Tower of Majority Lower Bounds
Authors: Pinkerton, James Carl IV
Advisors: Braverman, Mark
Contributors: Chudnovsky, Maria
Department: Mathematics
Class Year: 2015
Abstract: In this paper, we investigate lower bounds to algorithms solving the majority function tower problem. We explore this class of arguments, and examine several energy function. We find quadratic energy functions that produce lower bounds of (20/9)h ≈ 2.22h . Although short of the best known lower bound of (9/4)h = 2.25h , this technique coupled with better energy or advantage functions may provide a breakthrough.
Extent: 24 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2016

Files in This Item:
File SizeFormat 
PUTheses2015-Pinkerton_James_Carl_IV.pdf398.18 kBAdobe PDF    Request a copy

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