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.
Proceedings Title: Proceedings published by Springer-Verlag
Conference Dates: September 13, 2005
Conference Title: Latin American Theoretical Informatics Symposium
Pub Type: Conferences
circuit complexity, complexity, concrete complexity, cryptographic proofs, Hamming weight, multiplicative, symmetric functions