= Balanced finite-monoid reduction circuit
{title2=$\text{size }O(n),\quad\text{depth }O(\log n)$}
A fixed finite <monoid> operation has a constant-size Boolean truth-table <Boolean circuit> on its constant-bit encodings. Reduce $n$ elements in a balanced binary tree to get linear size and logarithmic depth. Associativity ensures that tree grouping does not change the product. <MOD3> uses addition in the three-element residue group, with input-position signs handled at the leaves.
Back to article page
