Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp012801pj641
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
URI: http://arks.princeton.edu/ark:/88435/dsp012801pj641
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2023

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.