Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
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|