Skip to main content
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.

Tight Bounds for the Multiplicative Complexity of Symmetric Functions

Published

Author(s)

Joan Boyar, Rene Peralta

Abstract

The multiplicative complexity of a Boolean function f is defined as the minimum number of binary conjunction (AND) gates required to construct a circuit representing f , when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the multiplicative complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. They are powerful enough to give exact multiplicative complexities for several classes of symmetric functions. In particular, the multiplicative complexity of computing the Hamming weight of n bits is shown to be exactly n − H^N(n), where H^N(n) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexities of basic symmetric functions and the fractal known as Sierpinski's gasket.
Citation
Theoretical Computer Science
Volume
396
Issue
1-3

Keywords

circuit complexity, cryptographic proofs, multi-party computation, multiplicative complexity, symmetric functions

Citation

Boyar, J. and Peralta, R. (2008), Tight Bounds for the Multiplicative Complexity of Symmetric Functions, Theoretical Computer Science, [online], https://doi.org/10.1016/j.tcs.2008.01.030, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=51208 (Accessed March 28, 2024)
Created April 27, 2008, Updated October 14, 2021