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/log2n)). 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.

Last modified: Mon Apr 15 10:00:43 CEST 2013