Constructions of Depth-2 Majority Circuits for Comparison and Addition using Linear Block Codes
Noga Alon, Jehoshua Bruck · 2005
We address the problem of computing the COMPARISON and ADDITION functions of two n-bit numbers using circuits of (nonmonotone) MAJORITY gates. Given n Boolean variables sl,. . . ,2;, E { -1, l}, a non-monotone MAJORITY gate (in the va.riables 2,) is a Boolean function whose value is the sign of E~z;, where each E, is either 1 or -1. We construct a.n explicit sparse polynomial whose sign computes the COMPAR,ISON function of two integers. Similar polynomials are constructed for computing all the bits of the summation of the two integers. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only non-monotone 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 n n-bit numbers (see [3] and [SI). A crucial ingredient in our a.pproach is the construction of a discrete version of a sparse polynomial-one that has a, large absolute value for a single a.ssignment and extremely small absolute values for all other assignments. We construct sparse delta polynomials using generator matrices of certain linear block codes. In the rest of this summa.ry we sketch the ideas rehted to the construction for the COMPARISON function. More details a.nd related results appea.r in [I].