Cancellation-Free Circuits in Unbounded and Bounded Depth

Joan Boyar, Magnus Gausdal Find

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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/log2 n). This improves on a recent result by Sergeev and Gashkov who have studied a similar problem. 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 Ω(nlogn) lower bound.
Original languageEnglish
Title of host publicationFundamentals of Computation : 19th International Symposium, FCT 2013
EditorsLeszek Gąsieniec, Frank Wolter
Publication date2013
ISBN (Print)978-3-642-40163-3
Publication statusPublished - 2013
Event19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, United Kingdom
Duration: 19. Aug 201321. Aug 2013
Conference number: 19


Conference19th International Symposium on Fundamentals of Computation Theory
LocationCrowne Plaza Hotel, Liverpool
Country/TerritoryUnited Kingdom
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Cancellation-Free Circuits in Unbounded and Bounded Depth'. Together they form a unique fingerprint.

Cite this