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.

Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions



Luis Brandao, Cagdas Calik, Meltem Sonmez Turan, Rene Peralta


A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195-201, 1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43-57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1-3), 223-246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions Σnk and counting functions Enk with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric Σ84 and the counting E84 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.
Cryptography and Communication


Symmetric Boolean functions, multiplicative complexity, logic minimization, upper bounds


Brandao, L. , Calik, C. , Sonmez Turan, M. and Peralta, R. (2019), Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions, Cryptography and Communication, [online],, (Accessed June 19, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created August 16, 2019, Updated October 12, 2021