Energy Function Arguments in Finding Tower of Majority Lower Bounds

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.