The Library
Parity helps to compute majority
Tools
Oliveira, Igor C., Santhanam, Rahul and Srinivasan, Srikanth (2019) Parity helps to compute majority. In: 34th Computational Complexity Conference (CCC 2019), New Brunswick, NJ, USA, 18-20 Jul 2019. Published in: Proceedings of the 34th Computational Complexity Conference (CCC), 137 23:1-23:17. ISBN 9783959771160. doi:10.4230/LIPIcs.CCC.2019.23 ISSN 1868-8969.
|
PDF
WRAP-parity-helps-compute-majority-Oliveira-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (574Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2019.23
Abstract
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})}.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Threshold logic | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | Proceedings of the 34th Computational Complexity Conference (CCC) | ||||||
Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | ||||||
ISBN: | 9783959771160 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 2019 | ||||||
Dates: |
|
||||||
Volume: | 137 | ||||||
Page Range: | 23:1-23:17 | ||||||
DOI: | 10.4230/LIPIcs.CCC.2019.23 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 11 November 2019 | ||||||
Date of first compliant Open Access: | 11 November 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 34th Computational Complexity Conference (CCC 2019) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | New Brunswick, NJ, USA | ||||||
Date(s) of Event: | 18-20 Jul 2019 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year