NIST logo

Publication Citation: The Exact Multiplicative Complexity of the Hamming Weight Function

NIST Authors in Bold

Author(s): Rene C. Peralta; Joan Boyar;
Title: The Exact Multiplicative Complexity of the Hamming Weight Function
Published: September 13, 2005
Abstract: We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for addition and multiplication modulo 2 (alternatively, XOR and conjunction gates) only. The number of multiplications necessary and sufficient to build such a circuit is called the multiplicative complexity of the Hamming weight function. We prove the exact multiplicative complexity of the Hamming weight function on n variables is n minus the Hamming weight of the binary representation of n.
Conference: Latin American Theoretical Informatics Symposium
Proceedings: Proceedings published by Springer-Verlag
Dates: September 13, 2005
Keywords: circuit complexity;complexity;concrete complexity;cryptographic proofs;Hamming weight;multiplicative;symmetric functions
Research Areas: Information Technology