  Recent improvements in adder optimization could be achieved by optimizing the
AND-trees occurring within the constructed circuits. The overlap of such trees
and its potential for pure size optimization has not been taken into account
though. Motivated by this, we examine the fundamental problem of minimizing the
size of a circuit for multiple AND-functions on intersecting variable sets. Our
formulation generalizes the overlapping \AND-trees within adder optimization
but is in NP, in contrast to general Boolean circuit optimization which is in
$\Sigma_2^p$ (and thus suspected not to be in NP). While restructuring the AND-
or XOR-trees simultaneously, we optimize the total number of gates needed for
all functions to be computed. We show that this problem is APX-hard already for
functions of few variables and present efficient approximation algorithms for
the case in which the Boolean functions depend on at most 3 or 4 variables
each, achieving guarantees of $\frac 43$ and $1.9$, respectively. To conclude,
we give a polynomial approximation algorithm with guarantee $\frac 23k$ for
AND-functions of up to $k$ variables. To achieve these results, the key
technique is to determine how much overlap among the variable sets makes tree
construction cheap and how little makes the optimum solution large.
