Cancellation-free circuits in unbounded and bounded depth ?
We study the notion of cancellation-free circuits. This is a restriction of 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 XOR circuit. We present a new proof showing that the difference can be a factor ?(n/log2?n) ? ( n / log 2 ? n ) . Furthermore, our proof holds for circuits of constant depth. We also study the complexity of computing the Sierpinski matrix using cancellation-free circuits and give a tight ?(nlog?(n)) ? ( n log ? ( n ) ) lower bound.
cancellation-free circuit complexity linear circuits