Concrete Multiplicative Complexity of Symmetric Functions

Joan Boyar, Rene Peralta

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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), where H(n) is the Hamming weight of the binary representation of n. We also show a close relationship between the complexity of symmetric functions and fractals derived from the parity of binomial coefficients.
OriginalsprogEngelsk
TitelMathematical Foundations of Computer Science 2006 : 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006. Proceedings
Antal sider11
Vol/bind4162
Publikationsdato2006
Sider179-189
DOI
StatusUdgivet - 2006
Begivenhed31st International Symposium on Mathematical Foundations of Computer Science 2006 (MFCS 2006) - High Tatras, Slovakiet
Varighed: 28. aug. 20061. sep. 2006
Konferencens nummer: 31

Konference

Konference31st International Symposium on Mathematical Foundations of Computer Science 2006 (MFCS 2006)
Nummer31
LandSlovakiet
ByHigh Tatras
Periode28/08/200601/09/2006
NavnLecture Notes in Computer Science
Vol/bind4162

Fingeraftryk

Dyk ned i forskningsemnerne om 'Concrete Multiplicative Complexity of Symmetric Functions'. Sammen danner de et unikt fingeraftryk.

Citationsformater