U.S. flag

An official website of the United States government

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.

PUBLICATIONS

The Exact Multiplicative Complexity of the Hamming Weight Function

Published

Author(s)

Rene C. Peralta, 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
Information technology

Citation

Peralta, R. and Boyar, J. (2005), The Exact Multiplicative Complexity of the Hamming Weight Function, Proceedings published by Springer-Verlag (Accessed June 7, 2023)

Created September 13, 2005, Updated February 19, 2017