Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators

Joan Boyar, Magnus Find

We continue to study the notion of cancellation-free linear circuits. We show that every matrix can be computed by a cancellation- free circuit, and almost all of these are at most…