TL;DR
The authors prove an optimal lower bound on the composition complexity of the Majority function, showing that computing $\mathrm{Maj}_n$ from $k$-local boolean functions requires at least $\Omega(\frac{n}{k} \log k)$ functions—an $\Omega(\log k)$ overhead over the ideal $n/k$. This result bypasses classic sensitivity barriers, reproves the optimal $\Omega(n \log n)$ length bound for bounded-width branching programs via an information-theoretic approach, and charts a new path toward breaking the decades-old $2^{\Omega(\sqrt{n})}$ barrier for depth-3 circuits.
What Problem Does This Paper Address?
In theoretical computer science, a natural strategy for computing a function $f$ is divide-and-conquer: compute $m$ simple "local" sub-functions $g_1, \dots, g_m$ (each querying at most $k \ll n$ bits), then combine them via an outer function $h$ such that $f(x) = h(g_1(x), \dots, g_m(x))$. The minimum $m$ required is the $k$-composition complexity ($\mathrm{CC}_k(f)$).
Because every input bit must be queried at least once, the trivial baseline is $\mathrm{CC}_k(f) \ge n/k$. For functions like $\mathrm{Parity}_n$, this bound is tight ($m = O(n/k)$). For $\mathrm{Maj}_n$, an upper bound of $O(\frac{n}{k} \log k)$ is easily obtained by computing the Hamming weight of $n/k$ disjoint blocks of size $k$ and adding them up. However, prior to this work, it was unknown whether any superconstant composition overhead was required—even proving a bound of $1.1(n/k)$ for Majority was open.
Resolving this question is directly tied to central open problems in circuit complexity:
- Bounded-width branching programs: Lower bounds on $\mathrm{CC}_k(f)$ directly translate to length bounds $L \ge \Omega(k \cdot \mathrm{CC}_k(f))$.
- Depth-3 circuits: The best known lower bound for depth-3 circuits computing Majority has been stuck at $2^{\Omega(\sqrt{n})}$ since the early 1990s. Improved composition lower bounds serve as a prerequisite to breaking this barrier.
Methods
The proof introduces two primary innovations:
- Information Theory & Mutual Information: Instead of classic combinatorial or Ramsey-theoretic arguments, the authors analyze the mutual information $I[X_i : g_1(X), \dots, g_m(X)]$ between an input bit $X_i$ and the inner functions' outputs on a uniform input $X$.
- Bootstrapping from Multi-Output Functions:
- The authors first analyze the Hamming Weight function ($\mathrm{HW}_n(x) = \sum x_i$), which outputs an integer in $\{0, \dots, n\}$.
- To transfer this result to the single-bit Majority function, they use a system of control variables (fixed bits used to adjust the threshold) and buffer variables (variables isolating the free inputs from control inputs so that no single $g_j$ queries both). This reduction forces Majority to act as a partial Hamming weight computer over a large slice of the hypercube without inflating the query budget.
Datasets
Not discussed in the paper. (This is a theoretical paper in computational complexity.)
Key Insights and Ideas
-
"The less it is queried, the more it is revealed": Counterintuitively, if an input bit $x_i$ is queried by very few inner functions ($q$ of them), the collective outputs of all inner functions must reveal significant information about $x_i$: $$\ I[X_i : g_1(X), \dots, g_m(X)] \ge 2^{-O(q)}.$$ Why? The $m - q$ functions that do not query $x_i$ can collectively take only a limited set of outputs. Conditioned on those outputs, the remaining $q$ functions can distinguish at most $2^q$ possible Hamming weights. Because flipping $x_i$ shifts the Hamming weight by exactly $\pm 1$, the sequence of weight probabilities must experience an "upward jump," making $x_i$ predictable with bias $2^{-O(q)}$ above random chance.
-
Escaping the Sensitivity Trap: Standard depth-3 circuit lower bounds depend on the sensitivity $s(f) \le n$, which hits a wall at $2^{\Omega(\sqrt{s(f)})} = 2^{\Omega(\sqrt{n})}$ (where Parity is maximally hard). Composition complexity separates Majority from Parity, identifying a structural weakness in Majority where Parity is easy.
- Multi-Output Stepping Stones: Proving lower bounds directly for single-bit functions is notoriously hard. Demonstrating that computing Majority implicitly entails computing a multi-output function (Hamming weight) enables the use of richer information-theoretic tools.
Key Results
-
Optimal Composition Bound: For any $\epsilon > 0$ and $k \le n^{1-\epsilon}$, $$\mathrm{CC}_k(\mathrm{Maj}_n) = \Theta\left(\frac{n}{k} \log k\right).$$ This establishes an optimal composition overhead of $\Theta(\log k)$.
-
Branching Program Complexity: Setting $k = \sqrt{n}$ immediately yields an alternate, communication-free proof of the classic theorem by Alon & Maass (1986) and Babai et al. (1990): any bounded-width branching program computing $\mathrm{Maj}_n$ requires length $\Omega(n \log n)$.
- Implications for Depth-3 Circuits: Standard divide-and-conquer constructions yield depth-3 circuits of size $2^{O(m + k)} = 2^{O(\sqrt{n \log n})}$. The paper's lower bound proves that $\max(\mathrm{CC}_k(\mathrm{Maj}_n), k) \ge \Omega(\sqrt{n \log n})$, formally demonstrating that any sub-$2^{O(\sqrt{n \log n})}$ depth-3 circuit cannot rely on this paradigm.
Limitations and Future Work
- Model Strength vs. Depth-3 Circuits: The result applies to arbitrary local boolean functions combined by an arbitrary gate. In depth-3 circuits, bottom gates have restricted types (AND/OR) but potentially larger effective fan-in. Bridging this gap is required to fully resolve the $2^{\omega(\sqrt{n})}$ depth-3 open problem.
- Proposed Conjectures:
- Conjecture 30 & 31: Lower bounds against representations where inner or outer functions are depth-$O(\sqrt{n})$ decision trees.
- Conjecture 32 (Random Linear Codes): The authors conjecture that random linear codes with $\ell$ parity checks require $\mathrm{CC}_k(f) \ge \Omega\left(\frac{n}{k} \frac{\ell}{\log(n/k)}\right)$, which would imply $2^{n^{1-\epsilon}}$ size lower bounds against $\Sigma_3$ circuits.
Summary updated