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

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Fundamentals of Computation : 19th International Symposium, FCT 2013
Redaktører	Leszek Gąsieniec, Frank Wolter
Forlag	Springer
Publikationsdato	2013
Sider	159-170
ISBN (Trykt)	978-3-642-40163-3
DOI	https://doi.org/10.1007/978-3-642-40164-0_17
Status	Udgivet - 2013
Begivenhed	19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, Storbritannien Varighed: 19. aug. 2013 → 21. aug. 2013 Konferencens nummer: 19

Konference

Konference	19th International Symposium on Fundamentals of Computation Theory
Nummer	19
Lokation	Crowne Plaza Hotel, Liverpool
Land/Område	Storbritannien
By	Liverpool
Periode	19/08/2013 → 21/08/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8070
ISSN	0302-9743

Emneord

circuit minimization
cancellation-free circuits
Sierpinski matrix
lower bounds

Dokumenter og links

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

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

2 Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

19th International Symposium on Fundamentals of Computation Theory
Find, M. G. (Deltager)
19. aug. 2013 → 21. aug. 2013
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i workshop, kursus, seminar eller lignende
19th International Symposium on Fundamentals of Computation Theory
Boyar, J. (Deltager)
19. aug. 2013 → 21. aug. 2013
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Citationsformater

@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. i L Gąsieniec & F Wolter (red), Fundamentals of Computation: 19th International Symposium, FCT 2013. Springer, Lecture Notes in Computer Science, bind 8070, s. 159-170, 19th International Symposium on Fundamentals of Computation Theory, Liverpool, Storbritannien, 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. red. / Leszek Gąsieniec; Frank Wolter. Springer, 2013. s. 159-170 (Lecture Notes in Computer Science, Bind 8070).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Relaterede aktiviteter

19th International Symposium on Fundamentals of Computation Theory

19th International Symposium on Fundamentals of Computation Theory

Citationsformater