Peralta, R.
and Boyar, J.
(2005),
The Exact Multiplicative Complexity of the Hamming Weight Function, Proceedings published by Springer-Verlag
(Accessed March 13, 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.
The Exact Multiplicative Complexity of the Hamming Weight Function
Published
Author(s)
, Joan Boyar
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.Proceedings Title
Proceedings published by Springer-Verlag
Conference Dates
September 13, 2005
Conference Title
Latin American Theoretical Informatics Symposium
Pub Type
Conferences
Keywords
circuit complexity, complexity, concrete complexity, cryptographic proofs, Hamming weight, multiplicative, symmetric functions
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.
Created September 13, 2005, Updated February 19, 2017