The Composition Complexity of Majority

Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan

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:

  1. 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))$.
  2. 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

Abstract

We study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {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 ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) 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 g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).
BibTeX
@inproceedings{lecomte2022composition,
  author = {Victor Lecomte and Prasanna Ramakrishnan and Li-Yang Tan},
  title = {{The Composition Complexity of Majority}},
  booktitle = {CCC},
  year = {2022},
  url = {https://openreview.net/forum?id=V5YxGtZCPKb},
}

Loading related content...

Figure