The composition complexity of majority

Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan

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…