Cancellation-Free Circuits in Unbounded and Bounded Depth

Joan Boyar; Magnus Gausdal Find

doi:10.1007/978-3-642-40164-0_17

Cancellation-Free Circuits in Unbounded and Bounded Depth

Joan Boyar, Magnus Gausdal Find

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

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/log² 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 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	159-170
ISBN (Print)	978-3-642-40163-3
DOIs	https://doi.org/10.1007/978-3-642-40164-0_17
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	0302-9743

Documents & Links

10.1007/978-3-642-40164-0_17

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

Cite this

@inproceedings{b7dbdb3985b14000824ca4358b1f90ae,

title = "Cancellation-Free Circuits in Unbounded and Bounded Depth",

abstract = "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.",

keywords = "circuit minimization, cancellation-free circuits, Sierpinski matrix, lower bounds",

author = "Joan Boyar and Find, {Magnus Gausdal}",

year = "2013",

doi = "10.1007/978-3-642-40164-0_17",

language = "English",

isbn = "978-3-642-40163-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "159--170",

editor = "Leszek G{\c a}sieniec and Frank Wolter",

booktitle = "Fundamentals of Computation",

address = "Germany",

note = "19th International Symposium on Fundamentals of Computation Theory ; Conference date: 19-08-2013 Through 21-08-2013",

}

Boyar, J & Find, MG 2013, Cancellation-Free Circuits in Unbounded and Bounded Depth. in L Gąsieniec & F Wolter (eds), Fundamentals of Computation: 19th International Symposium, FCT 2013. Springer, Lecture Notes in Computer Science, vol. 8070, pp. 159-170, 19th International Symposium on Fundamentals of Computation Theory, Liverpool, United Kingdom, 19/08/2013. https://doi.org/10.1007/978-3-642-40164-0_17

Cancellation-Free Circuits in Unbounded and Bounded Depth. / Boyar, Joan; Find, Magnus Gausdal.
Fundamentals of Computation: 19th International Symposium, FCT 2013. ed. / Leszek Gąsieniec; Frank Wolter. Springer, 2013. p. 159-170 (Lecture Notes in Computer Science, Vol. 8070).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Cancellation-Free Circuits in Unbounded and Bounded Depth

AU - Boyar, Joan

AU - Find, Magnus Gausdal

N1 - Conference code: 19

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - circuit minimization

KW - cancellation-free circuits

KW - Sierpinski matrix

KW - lower bounds

U2 - 10.1007/978-3-642-40164-0_17

DO - 10.1007/978-3-642-40164-0_17

M3 - Article in proceedings

SN - 978-3-642-40163-3

T3 - Lecture Notes in Computer Science

SP - 159

EP - 170

BT - Fundamentals of Computation

A2 - Gąsieniec, Leszek

A2 - Wolter, Frank

PB - Springer

T2 - 19th International Symposium on Fundamentals of Computation Theory

Y2 - 19 August 2013 through 21 August 2013

ER -

Cancellation-Free Circuits in Unbounded and Bounded Depth

Abstract

Conference

Documents & Links

Fingerprint

Related activities

19th International Symposium on Fundamentals of Computation Theory

19th International Symposium on Fundamentals of Computation Theory

Cite this