THE MULTIPLICATIVE COMPLEXITY OF QUADRATIC BOOLEAN FORMS

Let the multiplicative complexity L(f) of a boolean function f be the minimal number of and-gates that are sufficient to evaluate f by circuits over the basis AND, +, 1. We characterize the multiplicative complexity L(f) of quadratic boolean forms f; it is half the rank of an associated matrix. Two quadratic boolean forms f;g have the same complexity L(f)=L(g) iff they are isomorphic by a linear isomorphism. We characterize computational independence of two quadratic boolean forms f1, f2 in the sense that L(f1, f2) = L(f1) + L(f2).