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