Oliveira, Igor Carboni ;
Santhanam, Rahul ;
Srinivasan, Srikanth
Parity Helps to Compute Majority
Abstract
We study the complexity of computing symmetric and threshold functions by constantdepth 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 depthd AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d1)})}. By using a divideandconquer approach, it is easy to show that Majority can be computed with depthd AC^0[oplus] circuits of size 2^{O~(n^{1/(d1)})}. 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 depthd AC^0[oplus] circuits of size exp(O~(n^{2/3 * 1/(d4)})). Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the RazborovSmolensky lower bound to show that for d >= 3 Majority requires depthd AC^0[oplus] circuits of size 2^{Omega(n^{1/(2d4)})}. For depths d <= 4, we are able to refine our techniques to get almostoptimal bounds: the depth3 AC^0[oplus] circuit size of Majority is 2^{Theta~(n^{1/2})}, while its depth4 AC^0[oplus] circuit size is 2^{Theta~(n^{1/4})}.
BibTeX  Entry
@InProceedings{oliveira_et_al:LIPIcs:2019:10845,
author = {Igor Carboni Oliveira and Rahul Santhanam and Srikanth Srinivasan},
title = {{Parity Helps to Compute Majority}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {23:123:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10845},
URN = {urn:nbn:de:0030drops108453},
doi = {10.4230/LIPIcs.CCC.2019.23},
annote = {Keywords: Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority}
}
2019
Keywords: 

Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 