**Tight Bounds For the Multiplicative Complexity of Symmetric Functions***Joan Boyar, René Peralta*

TCS 2008.

The multiplicative complexity of a Boolean function *f* is defined
as the minimum number of binary conjunction (AND) gates required
to construct a circuit representing *f*, when only exclusive-or,
conjunction and negation gates may be used. This article explores
in detail the multiplicative complexity of symmetric Boolean
functions. New techniques that allow such exploration are
introduced. They are powerful enough to give exact multiplicative
complexities for several classes of symmetric functions.
In particular, the multiplicative complexity of computing the
Hamming weight of *n* is shown to be exactly *n-H(n)*, where
*H(n)* is the Hamming weight of the binary representation of *n*.
We also show a close relationship between the complexity of
symmetric functions and the fractal known as Sierpinski's gasket.

Last modified: Tue Jan 29 16:20:33 CET 2008 Joan Boyar (joan@imada.sdu.dk)