Fast Monotone Summation over Disjoint Sets

We study the problem of computing an ensemble of multiplesums where the summands in each sum are indexed by subsetsof size $p$ of an $n$-element ground set.More precisely, the task is to compute,for each subset of size $q$ of the ground set, thesum over the values of all subsetsof size $p$ that are {\em disjoint} from the subset of size $q$.We present an arithmetic circuit that, without subtraction, solves the problemusing $O((n^p+n^q)\log n)$ arithmetic gates, all monotone;for constant $p$, $q$ this is within the factor $\log n$ of theoptimal. The circuit design is based on viewingthe summation as a ``set nucleation'' task and using atree-projection approach to implement the nucleation.Applications include improved algorithms for counting heaviest $k$-paths in a weightedgraph, computing permanents of rectangular matrices, and dynamic feature selectionin machine learning.