Aarhus University Seal / Aarhus Universitets segl

Some results on uniform arithmetic circuit complexity

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Some results on uniform arithmetic circuit complexity. / Frandsen, Gudmund Skovbjerg; Valence, Mark; Barrington, David A. Mix.

In: Theory of Computing Systems, Vol. 27, No. 2, 1994, p. 105-124.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

Frandsen, GS, Valence, M & Barrington, DAM 1994, 'Some results on uniform arithmetic circuit complexity', Theory of Computing Systems, vol. 27, no. 2, pp. 105-124. https://doi.org/10.1007/BF01195199

APA

Frandsen, G. S., Valence, M., & Barrington, D. A. M. (1994). Some results on uniform arithmetic circuit complexity. Theory of Computing Systems, 27(2), 105-124. https://doi.org/10.1007/BF01195199

CBE

Frandsen GS, Valence M, Barrington DAM. 1994. Some results on uniform arithmetic circuit complexity. Theory of Computing Systems. 27(2):105-124. https://doi.org/10.1007/BF01195199

MLA

Frandsen, Gudmund Skovbjerg, Mark Valence and David A. Mix Barrington. "Some results on uniform arithmetic circuit complexity". Theory of Computing Systems. 1994, 27(2). 105-124. https://doi.org/10.1007/BF01195199

Vancouver

Frandsen GS, Valence M, Barrington DAM. Some results on uniform arithmetic circuit complexity. Theory of Computing Systems. 1994;27(2):105-124. https://doi.org/10.1007/BF01195199

Author

Frandsen, Gudmund Skovbjerg ; Valence, Mark ; Barrington, David A. Mix. / Some results on uniform arithmetic circuit complexity. In: Theory of Computing Systems. 1994 ; Vol. 27, No. 2. pp. 105-124.

Bibtex

@article{1cb9588f297e44a680a3261dce9f7e8f,
title = "Some results on uniform arithmetic circuit complexity",
abstract = "We introduce a natural set of arithmetic expressions and define the complexity class AE to consist of all those arithmetic functions (over the fieldsF 2n) that are described by these expressions. We show that AE coincides with the class of functions that are computable with constant depth and polynomial-size unbounded fan-in arithmetic circuits satisfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-input and 1-output arithmetic function over the fieldsF2n may be identified with ann-input andn-output Boolean function when field elements are represented as bit strings. We prove that if some such representation is X-uniform (where X is P or DLOGTIME), then the arithmetic complexity of a function (measured with X-uniform unbounded fan-in arithmetic circuits) is identical to the Boolean complexity of this function (measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properties.",
author = "Frandsen, {Gudmund Skovbjerg} and Mark Valence and Barrington, {David A. Mix}",
year = "1994",
doi = "10.1007/BF01195199",
language = "English",
volume = "27",
pages = "105--124",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer",
number = "2",

}

RIS

TY - JOUR

T1 - Some results on uniform arithmetic circuit complexity

AU - Frandsen, Gudmund Skovbjerg

AU - Valence, Mark

AU - Barrington, David A. Mix

PY - 1994

Y1 - 1994

N2 - We introduce a natural set of arithmetic expressions and define the complexity class AE to consist of all those arithmetic functions (over the fieldsF 2n) that are described by these expressions. We show that AE coincides with the class of functions that are computable with constant depth and polynomial-size unbounded fan-in arithmetic circuits satisfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-input and 1-output arithmetic function over the fieldsF2n may be identified with ann-input andn-output Boolean function when field elements are represented as bit strings. We prove that if some such representation is X-uniform (where X is P or DLOGTIME), then the arithmetic complexity of a function (measured with X-uniform unbounded fan-in arithmetic circuits) is identical to the Boolean complexity of this function (measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properties.

AB - We introduce a natural set of arithmetic expressions and define the complexity class AE to consist of all those arithmetic functions (over the fieldsF 2n) that are described by these expressions. We show that AE coincides with the class of functions that are computable with constant depth and polynomial-size unbounded fan-in arithmetic circuits satisfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-input and 1-output arithmetic function over the fieldsF2n may be identified with ann-input andn-output Boolean function when field elements are represented as bit strings. We prove that if some such representation is X-uniform (where X is P or DLOGTIME), then the arithmetic complexity of a function (measured with X-uniform unbounded fan-in arithmetic circuits) is identical to the Boolean complexity of this function (measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properties.

U2 - 10.1007/BF01195199

DO - 10.1007/BF01195199

M3 - Journal article

VL - 27

SP - 105

EP - 124

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -