Bounded depth arithmetic circuits: Counting and closure

Eric Allender; Andris Ambainis; David A.Mix Barrington; Samir Datta; Huong Lêthanh

doi:10.1007/3-540-48523-6_12

Bounded depth arithmetic circuits: Counting and closure

Eric Allender, Andris Ambainis, David A.Mix Barrington, Samir Datta, Huong Lêthanh

School of Arts and Sciences, Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

17 Scopus citations

Abstract

Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC⁰ and GapAC⁰. These function classes in turn provide new characterizati- ons of the computational power of threshold circuits, and provide a link between the circuit classes AC⁰ (where many lower bounds are known) and TC⁰ (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC⁰ and GapAC⁰ and characterize #AC⁰ in terms of counting paths in a family of bounded-width graphs.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings
Publisher	Springer Verlag
Pages	149-158
Number of pages	10
ISBN (Print)	3540662243, 9783540662242
DOIs	https://doi.org/10.1007/3-540-48523-6_12
State	Published - 1999
Event	26th International Colloquium on Automata, Languages and Programming, ICALP 1999 - Prague, Czech Republic Duration: Jul 11 1999 → Jul 15 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1644 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	26th International Colloquium on Automata, Languages and Programming, ICALP 1999
Country/Territory	Czech Republic
City	Prague
Period	7/11/99 → 7/15/99

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-48523-6_12

Cite this

Allender, E., Ambainis, A., Barrington, D. A. M., Datta, S., & Lêthanh, H. (1999). Bounded depth arithmetic circuits: Counting and closure. In Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings (pp. 149-158). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1644 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-48523-6_12

Allender, Eric ; Ambainis, Andris ; Barrington, David A.Mix et al. / Bounded depth arithmetic circuits : Counting and closure. Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings. Springer Verlag, 1999. pp. 149-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e51d237b7cc4438b92c6b7f03c820281,

title = "Bounded depth arithmetic circuits: Counting and closure",

abstract = "Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC0 and GapAC0. These function classes in turn provide new characterizati- ons of the computational power of threshold circuits, and provide a link between the circuit classes AC0 (where many lower bounds are known) and TC0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC0 and GapAC0 and characterize #AC0 in terms of counting paths in a family of bounded-width graphs.",

author = "Eric Allender and Andris Ambainis and Barrington, {David A.Mix} and Samir Datta and Huong L{\^e}thanh",

year = "1999",

doi = "10.1007/3-540-48523-6_12",

language = "English (US)",

isbn = "3540662243",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "149--158",

booktitle = "Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings",

address = "Germany",

note = "26th International Colloquium on Automata, Languages and Programming, ICALP 1999 ; Conference date: 11-07-1999 Through 15-07-1999",

}

Allender, E, Ambainis, A, Barrington, DAM, Datta, S & Lêthanh, H 1999, Bounded depth arithmetic circuits: Counting and closure. in Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1644 LNCS, Springer Verlag, pp. 149-158, 26th International Colloquium on Automata, Languages and Programming, ICALP 1999, Prague, Czech Republic, 7/11/99. https://doi.org/10.1007/3-540-48523-6_12

Bounded depth arithmetic circuits: Counting and closure. / Allender, Eric; Ambainis, Andris; Barrington, David A.Mix et al.
Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings. Springer Verlag, 1999. p. 149-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1644 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Bounded depth arithmetic circuits

T2 - 26th International Colloquium on Automata, Languages and Programming, ICALP 1999

AU - Allender, Eric

AU - Ambainis, Andris

AU - Barrington, David A.Mix

AU - Datta, Samir

AU - Lêthanh, Huong

PY - 1999

Y1 - 1999

N2 - Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC0 and GapAC0. These function classes in turn provide new characterizati- ons of the computational power of threshold circuits, and provide a link between the circuit classes AC0 (where many lower bounds are known) and TC0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC0 and GapAC0 and characterize #AC0 in terms of counting paths in a family of bounded-width graphs.

AB - Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC0 and GapAC0. These function classes in turn provide new characterizati- ons of the computational power of threshold circuits, and provide a link between the circuit classes AC0 (where many lower bounds are known) and TC0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC0 and GapAC0 and characterize #AC0 in terms of counting paths in a family of bounded-width graphs.

UR - http://www.scopus.com/inward/record.url?scp=84887465752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887465752&partnerID=8YFLogxK

U2 - 10.1007/3-540-48523-6_12

DO - 10.1007/3-540-48523-6_12

M3 - Conference contribution

AN - SCOPUS:84887465752

SN - 3540662243

SN - 9783540662242

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 149

EP - 158

BT - Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings

PB - Springer Verlag

Y2 - 11 July 1999 through 15 July 1999

ER -

Allender E, Ambainis A, Barrington DAM, Datta S, Lêthanh H. Bounded depth arithmetic circuits: Counting and closure. In Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings. Springer Verlag. 1999. p. 149-158. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-48523-6_12

Bounded depth arithmetic circuits: Counting and closure

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this