Boolean circuits versus arithmetic circuits
type: Item
instance of: scholarly article
title: Boolean circuits versus arithmetic circuits
zbMATH Open document ID: 0718.11064
DOI: 10.1016/0890-5401(91)90078-G
author: Joachim von zur Gathen
author: Gadiel Seroussi
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
review text: The authors compare the two computational models of Boolean circuits and arithmetic circuits for the computation of polynomials over the rationals and over finite fields. In the case of finite fields separate treatments are given for the cases of large and small characteristics. As the goal of the paper is to survey the literature and to compare the effectiveness of these two models of computations, few proofs are given.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11Y40
zbMATH DE Number: 4183544
zbMATH Keywords: Boolean circuits
zbMATH Keywords: arithmetic circuits
zbMATH Keywords: polynomials
zbMATH Keywords: finite fields
zbMATH Keywords: survey
reviewed by: Gary L. Mullen
MaRDI profile type: Publication
cites work: Q4091421
cites work: Log Depth Circuits for Division and Related Problems
cites work: Q3962468
cites work: Fast parallel matrix and GCD computations
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Very Fast Parallel Polynomial Arithmetic
cites work: The parallel complexity of exponentiating polynomials over finite fields
cites work: Parallel Algorithms for Algebraic Problems
cites work: Irreducibility of multivariate polynomials
cites work: Q4725742
cites work: Computing Powers in Parallel
cites work: Inversion in finite fields using logarithmic depth
cites work: Q4339908
cites work: Q3691587
cites work: On the power of straight- line computations in finite fields
cites work: Q5690468
cites work: Q3798224
cites work: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
cites work: Finite monoids and the fine structure of NC 1
cites work: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
cites work: On uniform circuit complexity
cites work: Factoring numbers in O(log n) arithmetic steps
cites work: Berechnung und Programm. I
cites work: Q4047029
cites work: The Computational Complexity of Continued Fractions
cites work: The complexity of computing the permanent
cites work: Q3929052
cites work: Fast Parallel Computation of Polynomials Using Few Processors
description: scientific article