
Summary: All Boolean variables here range over the two-element set \(\{-1,1\}\). Given \(n\) Boolean variables \(x_ 1, \dots, x_ n\) a nonmonotone MAJORITY gate (in the variables \(x_ i)\) is a Boolean function whose value is the sign of \(\sum^ n_{i = 1} \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 \geq 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 \(n\) \(n\)-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.
majority circuits, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), error-correcting codes, Switching theory, application of Boolean algebra; Boolean functions, comparison function, addition function, Linear codes (general theory), threshold function
majority circuits, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), error-correcting codes, Switching theory, application of Boolean algebra; Boolean functions, comparison function, addition function, Linear codes (general theory), threshold function
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
