Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
Noga Alon, Jehoshua Bruck · SIAM Journal on Discrete Mathematics · 1994
All Boolean variables here range over the two-element set $\{ - 1,1 \}$. Given n Boolean variables $x_1 , \ldots ,x_n $, a nonmonotone MAJORITY gate (in the variables $x_i $) is a Boolean function whose value is the sign of $\Sigma _{i = 1}^n \varepsilon _i x_i $, where each $ \varepsilon _i $ is either 1 or $ - 1$. The COMPARISON function is the Boolean function of two n-bits integers X and Y whose value is $ - 1$ if and only if $X\geqq Y$. An explicit sparse polynomial whose sign computes this function is constructed. Similar polynomials are constructed for computing all the bits of the summation of the two numbers X and Y. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only nonmonotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best-known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of nn-bit numbers. A crucial ingredient is the construction of a discrete version of a sparse “delta polynomial”—one that has a large absolute value for a single assignment and extremely small absolute values for all other assignments.