# Commutative operation benefits

With an associative operation I can rewrite a computation tree

        +
/ \
+   4
/ \
+   3
/ \
+   2
/ \
0   1


to be more efficient in parallel.

     +
/   \
+     +
/ \   / \
1   2 3   4


Are there situations where assuming commutativity offers computation benefits?

• Isn't commutativity exploited (required?) by MapReduce? (E.g. courses.cs.washington.edu/courses/cse490h/08au/lectures/…) Maybe somebody who knows more can elaborate. Jul 7 at 20:22
• I'd expect commutative operations on sparse structures to be often optimizable by commutativity, but I can't find a good example Jul 7 at 20:35

One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $$n \times n$$ determinant must have size $$2^{\Omega(n)}$$. On the other hand, the determinant is computable by commutative algebraic formulas of size $$n^{O(\log n)}$$.