Welcome to the resource topic for 2019/708
Title:
Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions
Authors: Luís T. A. N. Brandão, Çağdaş Çalık, Meltem Sönmez Turan, René Peralta
Abstract: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 (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 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 \Sigma^n_k and counting functions E^n_k with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric \Sigma^8_4 and the counting E^8_4 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.
ePrint: https://eprint.iacr.org/2019/708
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .