Fast monotone summation over disjoint sets ?
We study evaluation of sums indexed by input sets that are disjoint from output sets. For indices over all small subsets, we show a near-linear monotone complexity. Applications include counting maximum-weight paths and rectangular matrix permanents.
matrix permanent algorithms arithmetic complexity commutative semigroup disjoint summation k-path