**Cancellation-Free Circuits in Unbounded and Bounded Depth***Joan Boyar and Magnus Find*

FCT 2013.

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 studied models of computation.
The notion was coined by Boyar and Peralta in a study of heuristics
for a particular circuit minimization problem.
They asked how large a gap there can be between
the smallest cancellation-free circuit and the smallest linear
circuit.
We show that
the difference can be a factor Ω(n/log^{2}n)).
This
improves on an independently obtained result by Sergeev and Gashkov
who have studied a similar problem.
Furthermore, our proof generalizes to circuits of bounded depth.
We also study the cancellation-free complexity of a particular
matrix family, namely the Sierpinski matrix.
We give a Ω(n log n) lower bound for the Sierpinski
matrix in this model.