Logarithmic Depth Circuits for Algebraic Functions
From MaRDI portal
Publication:3750999
DOI10.1137/0215017zbMath0611.68014OpenAlexW2126466445MaRDI QIDQ3750999
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
parallel computationpolynomialsdiscrete Fourier transformpower serieselementary functionsBoolean circuitscircuit depthalgebraic computationinteger divisionalgebraic circuits
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-uniformNC1 ⋮ 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
