2026-08-16T08:54:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16581 2024-03-06T10:57:51Z ddc:004 open_access

The Composition Complexity of Majority Lecomte, Victor Ramakrishnan, Prasanna Tan, Li-Yang computational complexity circuit lower bounds 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Victor Lecomte and Prasanna Ramakrishnan and Li-Yang Tan 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.19 urn:nbn:de:0030-drops-165818 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.19 eng https://creativecommons.org/licenses/by/4.0/legalcode