Activities per year
Abstract
We study the notion of “cancellationfree” circuits. This is a restriction of linear Boolean circuits (XORcircuits), 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 cancellationfree circuit and the smallest linear circuit. We show that the difference can be a factor Ω(n/log^{2} 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 cancellationfree circuits and give a tight Ω(nlogn) lower bound.
Original language  English 

Title of host publication  Fundamentals of Computation : 19th International Symposium, FCT 2013 
Editors  Leszek Gąsieniec, Frank Wolter 
Publisher  Springer 
Publication date  2013 
Pages  159170 
ISBN (Print)  9783642401633 
DOIs  
Publication status  Published  2013 
Event  19th International Symposium on Fundamentals of Computation Theory  Crowne Plaza Hotel, Liverpool, Liverpool, United Kingdom Duration: 19. Aug 2013 → 21. Aug 2013 Conference number: 19 
Conference
Conference  19th International Symposium on Fundamentals of Computation Theory 

Number  19 
Location  Crowne Plaza Hotel, Liverpool 
Country/Territory  United Kingdom 
City  Liverpool 
Period  19/08/2013 → 21/08/2013 
Series  Lecture Notes in Computer Science 

Volume  8070 
ISSN  03029743 
Fingerprint
Dive into the research topics of 'CancellationFree Circuits in Unbounded and Bounded Depth'. Together they form a unique fingerprint.Related Activities
 2 Organisation or participation in workshops, courses or seminars

19th International Symposium on Fundamentals of Computation Theory
Joan Boyar (Participant)
19. Aug 2013 → 21. Aug 2013Activity: Attending an event › Organisation or participation in workshops, courses or seminars

19th International Symposium on Fundamentals of Computation Theory
Magnus Gausdal Find (Participant)
19. Aug 2013 → 21. Aug 2013Activity: Attending an event › Organisation or participation in workshops, courses or seminars