The composition complexity of majority

Download PDF

We study the complexity of computing majority as a composition of local functions:

Majn=h(g1,…,gm),

where each gj:{0,1}n→{0,1} is an arbitrary function that queries only k≪n variables and h:{0,1}m→{0,1} is an arbitrary combining function. We prove an optimal lower bound of

m≥Ω(nklogk)

on the number of functions needed, which is a factor Ω(logk) larger than the ideal m=n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority.
Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits.
Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions gj, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).