Logarithmic Depth Circuits for Algebraic Functions

DOI10.1137/0215017zbMath0611.68014OpenAlexW2126466445MaRDI QIDQ3750999

John H. Reif

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215017

zbMATH Keywords

parallel computationpolynomialsdiscrete Fourier transformpower serieselementary functionsBoolean circuitscircuit depthalgebraic computationinteger divisionalgebraic circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (32)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Bits and relative order from residues, space efficiently ⋮ Polynomial division and its computational complexity ⋮ Inversion in finite fields using logarithmic depth ⋮ Ranking and formal power series ⋮ A logarithmic Boolean time algorithm for parallel polynomial division ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ Efficient parallel circuits and algorithms for division ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Parallel Hermite interpolation: An algebraic approach ⋮ Counting problems and algebraic formal power series in noncommuting variables ⋮ Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\) ⋮ Parallel models of computation: An introductory survey ⋮ A parallel method for fast and practical high-order Newton interpolation ⋮ A Complete Characterization of Unitary Quantum Space ⋮ Circuits for computing the GCD of two polynomials over an algebraic number field ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ Highly parallel computations modulo a number having only small prime factors ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ On iterated integer product ⋮ New algorithms for polynomial and trigonometric interpolation on parallel computers ⋮ Root finding with threshold circuits ⋮ Division in logspace-uniformNC¹ ⋮ Fast computation of divided differences and parallel Hermite interpolation ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ Planar acyclic computation ⋮ Effective entropies and data compression ⋮ Fast parallel algorithms for polynomial division over an arbitrary field of constants ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Computing a context-free grammar-generating series ⋮ Parallel algorithms for matrix polynomial division ⋮ A div(n) depth Boolean circuit for smooth modular inverse

This page was built for publication: Logarithmic Depth Circuits for Algebraic Functions