Name
Abstract | ||
|---|---|---|
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each $g_j :\{0,1\}^{n} \to \{0,1\}$ is an arbitrary function that queries only $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, which is a factor $\Omega(\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). |
Year | DOI | Venue |
|---|---|---|
2022 | 10.4230/LIPICS.CCC.2022.19 | Computational Complexity Conference (CCC) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Lecomte | 1 | 0 | 0.68 |
| Prasanna Ramakrishnan | 2 | 0 | 0.68 |
| Li-Yang Tan | 3 | 0 | 2.37 |