License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.19
URN: urn:nbn:de:0030-drops-165818
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16581/
Lecomte, Victor ;
Ramakrishnan, Prasanna ;
Tan, Li-Yang
The Composition Complexity of Majority
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 - Entry
@InProceedings{lecomte_et_al:LIPIcs.CCC.2022.19,
author = {Lecomte, Victor and Ramakrishnan, Prasanna and Tan, Li-Yang},
title = {{The Composition Complexity of Majority}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {19:1--19:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-241-9},
ISSN = {1868-8969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16581},
URN = {urn:nbn:de:0030-drops-165818},
doi = {10.4230/LIPIcs.CCC.2022.19},
annote = {Keywords: computational complexity, circuit lower bounds}
}
Keywords: |
|
computational complexity, circuit lower bounds |
Collection: |
|
37th Computational Complexity Conference (CCC 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
11.07.2022 |