Cancellation-Free Circuits in Unbounded and Bounded Depth

Joan Boyar, Magnus Find

We study the notion of "cancellation-free" circuits. This is a restriction of linear Boolean circuits (XOR circuits), but can be considered as being equivalent to previously studie…