Published: April 28, 2008
Citation: Theoretical Computer Science vol. 396, no. 42372, (May 10, 2008) pp. 223-246
Author(s)
Joan Boyar (University of Southern Denmark), Rene Peralta (NIST)
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 bits is shown to be exactly n-H^N (n), where H^N (n) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexities of basic symmetric functions and the fractal known as Sierpinski’s gasket.
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...
See full abstract
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 bits is shown to be exactly n-H^N (n), where H^N (n) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexities of basic symmetric functions and the fractal known as Sierpinski’s gasket.
Hide full abstract
Keywords
circuit complexity; cryptographic proofs; multi-party computation; multiplicative complexity; symmetric functions
Control Families
None selected
