Boyar, J.
and Peralta, R.
(2006),
Concrete Multiplicative Complexity of Symmetric Functions, MFCS 2006, , 1, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50828
(Accessed November 19, 2025)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Concrete Multiplicative Complexity of Symmetric Functions
Published
Author(s)
Joan Boyar,
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-Hnum(n), where Hnum(n) is the Hamming weight of the binary representation of n. We also show an intriguing relationship between the complexities of symmetric functions and fractals derived from the parities of binomial coefficients.Conference Location
, 1
Conference Title
MFCS 2006
Pub Type
Conferences
Download Paper
Keywords
circuit complexity, cryptographic proofs, multiplicative complexity, symmetric functions
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created July 31, 2006, Updated October 12, 2021