Princeton University Library Catalog

Energy Function Arguments in Finding Tower of Majority Lower Bounds

Author/​Artist:
Pinkerton, James Carl IV [Browse]
Format:
Senior thesis
Language:
English
Advisor(s):
Braverman, Mark [Browse]
Contributor(s):
Chudnovsky, Maria [Browse]
Department:
Princeton University. Department of Mathematics [Browse]
Class year:
2015
Description:
24 pages
Summary note:
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.