2026-08-18T13:37:08Z https://drops.dagstuhl.de/oai

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

Parity Helps to Compute Majority Oliveira, Igor Carboni Santhanam, Rahul Srinivasan, Srikanth Computational Complexity Boolean Circuits Lower Bounds Parity Majority We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC^0[oplus] circuits. Razborov [Alexander A. Razborov, 1987] and Smolensky [Roman Smolensky, 1987; Roman Smolensky, 1993] showed that Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d-1)})}. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-d AC^0[oplus] circuits of size 2^{O~(n^{1/(d-1)})}. This gap between upper and lower bounds has stood for nearly three decades. Somewhat surprisingly, we show that neither the upper bound nor the lower bound above is tight for large d. We show for d >= 5 that any symmetric function can be computed with depth-d AC^0[oplus] circuits of size exp(O~(n^{2/3 * 1/(d-4)})). Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the Razborov-Smolensky lower bound to show that for d >= 3 Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/(2d-4)})}. For depths d <= 4, we are able to refine our techniques to get almost-optimal bounds: the depth-3 AC^0[oplus] circuit size of Majority is 2^{Theta~(n^{1/2})}, while its depth-4 AC^0[oplus] circuit size is 2^{Theta~(n^{1/4})}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Igor Carboni Oliveira and Rahul Santhanam and Srikanth Srinivasan 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.23 urn:nbn:de:0030-drops-108453 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.23 eng https://creativecommons.org/licenses/by/3.0/legalcode