Cancellation-Free Circuits in Unbounded and Bounded Depth

Joan Boyar, Magnus Gausdal Find

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelFundamentals of Computation : 19th International Symposium, FCT 2013
RedaktørerLeszek Gąsieniec, Frank Wolter
ForlagSpringer
Publikationsdato2013
Sider159-170
ISBN (Trykt)978-3-642-40163-3
DOI
StatusUdgivet - 2013
Begivenhed19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, Storbritannien
Varighed: 19. aug. 201321. aug. 2013
Konferencens nummer: 19

Konference

Konference19th International Symposium on Fundamentals of Computation Theory
Nummer19
LokationCrowne Plaza Hotel, Liverpool
LandStorbritannien
ByLiverpool
Periode19/08/201321/08/2013
NavnLecture Notes in Computer Science
Vol/bind8070
ISSN0302-9743

Emneord

  • circuit minimization
  • cancellation-free circuits
  • Sierpinski matrix
  • lower bounds

Fingeraftryk

Dyk ned i forskningsemnerne om 'Cancellation-Free Circuits in Unbounded and Bounded Depth'. Sammen danner de et unikt fingeraftryk.

Citationsformater