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

surveyfinite fieldspolynomialsarithmetic circuitsBoolean circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Algebraic number theory computations (11Y40)

Related Items

Computing Frobenius maps and factoring polynomials, Inversion in finite fields using logarithmic depth, Polar varieties, real equation solving, and data structures: the hypersurface case, Parallel evaluation of arithmetic circuits, Feasible arithmetic computations: Valiant's hypothesis, Univariate polynomial factorization over finite fields with large extension degree, Efficient and optimal exponentiation in finite fields, Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Modular composition via factorization, A super-quadratic lower bound for depth four arithmetic circuits, Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\), The enumerability of P collapses P to NC

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