On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1)

AbstractThe multiplicative complexity c∧(f) of a Boolean function f is the minimum number of AND gates in a circuit representing f which employs only AND, XOR and NOT gates. A constructive upper bound, c∧(f)=2(n/2)+1−n/2−2, for any Boolean function f on n variables (n even) is given. A counting argument gives a lower bound of c∧(f)=2(n/2)−O(n). Thus we have shown a separation, by an exponential factor, between worst-case Boolean complexity (which is known to be Θ(2nn−1)) and worst-case multiplicative complexity. A construction of circuits for symmetric Boolean functions on n variables, requiring less than n+3n AND gates, is described