Boolean circuits versus arithmetic circuits

DOI10.1016/0890-5401(91)90078-GzbMath0718.11064MaRDI QIDQ2639101

Joachim von zur Gathen, Gadiel Seroussi

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

survey; finite fields; polynomials; arithmetic circuits; Boolean circuits

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11Y16: Number-theoretic algorithms; complexity

11T06: Polynomials over finite fields

11Y40: Algebraic number theory computations

Related Items

Efficient and optimal exponentiation in finite fields, Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Feasible arithmetic computations: Valiant's hypothesis, Polar varieties, real equation solving, and data structures: the hypersurface case, Parallel evaluation of arithmetic circuits, Computing Frobenius maps and factoring polynomials, The enumerability of P collapses P to NC, Inversion in finite fields using logarithmic depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Irreducibility of multivariate polynomials
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• On uniform circuit complexity
• Factoring numbers in O(log n) arithmetic steps
• Berechnung und Programm. I
• Inversion in finite fields using logarithmic depth
• Fast Parallel Computation of Polynomials Using Few Processors
• Parallel Algorithms for Algebraic Problems
• The Computational Complexity of Continued Fractions
• Very Fast Parallel Polynomial Arithmetic
• A taxonomy of problems with fast parallel algorithms
• Log Depth Circuits for Division and Related Problems
• Computing Powers in Parallel
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• The parallel complexity of exponentiating polynomials over finite fields
• Finite monoids and the fine structure of NC ¹
• On the power of straight- line computations in finite fields
• Fast parallel matrix and GCD computations