Parity helps to compute Majority

摘要

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC 0 [ ] circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth- d AC 0 [ ] circuits of size 2 ( 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 [ ] 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 [ ] circuits of size exp ( O ( n 3 2 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 [ ] circuits of size 2 ( n 1 (2 d ? 4) ) . For depths d 4 , we are able to refine our techniques to get almost-optimal bounds: the depth- 3 AC 0 [ ] circuit size of Majority is 2 ( n 1 2 ) , while its depth- 4 AC 0 [ ] circuit size is 2 ( n 1 4 ) .