On the Multiplicative Complexity of Boolean Functions

Abstract

The multiplicative complexity μ(f) of a Boolean function f is the smallest number of & (of AND gates) in circuits in the basis {x&y, x⊕y, 1} such that each circuit implements the function f. By μ(S) we denote the number of & (of AND gates) in a circuit S in the basis {x&y, x ⊕ y, 1}. We present a method to construct circuits in the basis {x&y, x ⊕ y, 1} for Boolean functions. By this method, for an arbitrary function f(x₁, . . . , x_n), we can construct a circuit S_f implementing the function f such that μ(S_f) ≤ (3/2 + o(1)) · 2^n/2, if n is even, and μ(S_f) ≤ (√2 + o(1))2^n/2, if n is odd. These evaluations improve estimations from [1].