Abstract
We study the complexity of computing the majority function as a composition of local functions: $Maj_n = h(g_1, \ldots, g_m)$, where each $g_j : \{0,1\}^n \to \{0,1\}$ is an arbitrary function that queries at most $k \ll n$ variables and $h : \{0,1\}^m \to \{0,1\}$ is an arbitrary combining function. We prove an optimal lower bound of $m \ge \Omega\left( \frac{n}{k} \log k \right)$ on the number of functions needed. This result reveals a factor of $\Omega(\log k)$ larger than the trivial $n/k$ bound, which we define as the "composition overhead." Our proof utilizes sharp bounds on information loss and a bootstrapping technique that translates lower bounds from multi-output functions (Hamming weight) to single-output functions (majority). This work recovers the best-known lower bounds for bounded-width branching programs and provides a roadmap for breaking long-standing barriers in small-depth boolean circuit complexity.
Introduction
A fundamental pursuit in computational complexity is understanding how global properties of data can be synthesized from local observations. This is formally captured by the concept of composition complexity ($CC_k(f)$), which measures the minimum number of $k$-local functions—functions that only "see" $k$ input bits—required to compute a target function $f$.
For the Majority function ($MAJ_n$), which outputs 1 if at least half the input bits are 1, a naive lower bound is $n/k$, as every bit must be queried at least once. However, whether Majority requires significantly more than this "ideal" number of components remained an open question. This paper establishes that Majority inherently incurs a logarithmic composition overhead, proving that $CC_k(MAJ_n) = \Theta(\frac{n}{k} \log k)$.
The Information-Theoretic Approach
The core of the proof rests on a novel information-theoretic analysis of "leakage." Traditional complexity measures often struggle with Majority because it lacks the rigid algebraic structure of functions like Parity. To overcome this, the authors developed a "Key Lemma" regarding mutual information.
The Sparsity-Information Trade-off
The proof demonstrates a counterintuitive relationship: if an input variable is queried by only a few inner functions $g_j$, those functions must collectively reveal a significant amount of information about that variable's value. In essence, the less a bit is queried, the more "informative" each query must be to preserve the bit's contribution to the final Majority result. By applying the subadditivity of entropy, the authors sum these individual information leaks to establish a global lower bound on the number of required functions $m$.
Multi-Output Bootstrapping
Proving lower bounds for single-output functions like Majority is notoriously difficult. The authors simplify the problem by first proving a tight lower bound for the Hamming Weight function, which outputs the total count of 1s in the input (requiring $\log n$ bits of output).
To transfer this result back to Majority, they employ a reduction toolkit involving:
- Control Variables: These are used to shift the input distribution, forcing the Majority function to effectively "count" and thus behave like the Hamming Weight function.
- Buffer Variables: These isolate different sets of inputs, ensuring that the reduction does not artificially inflate the number of required functions, thereby maintaining the integrity of the lower bound.
Significance and Implications
Majority vs. Parity
One of the most significant conceptual insights is the distinction between Majority and Parity. While Parity can be composed with zero overhead ($CC_k(Parity) = n/k$), Majority cannot. Many traditional complexity techniques (such as sensitivity or Fourier analysis) often treat Parity as the "hardest" function. This paper highlights why those techniques fail to provide strong bounds for models where Majority is the more complex operator.
Branching Programs and Circuit Complexity
As a direct corollary, the authors recover the best-known lower bound for bounded-width branching programs computing Majority: $\Omega(n \log n)$. While this bound was previously known, the new proof is entirely different, replacing classic Ramsey-theoretic arguments with a more flexible information-theoretic framework.
Furthermore, this work is positioned as a "necessary first step" toward breaking the $2^{\Omega(\sqrt{n})}$ size barrier for depth-3 circuits computing Majority. This problem has seen little progress in over three decades, and the authors propose that their composition complexity framework provides the right tools to finally tackle it.
Conclusion and Future Work
This paper settles the composition complexity of Majority and introduces a robust roadmap for future circuit complexity research. The authors suggest that the next challenges involve extending these bounds to more structured inner functions, such as small-depth decision trees, and applying the information-theoretic toolbox to random linear error-correcting codes, which are conjectured to be "hard" for small-depth circuits.
Summary updated