Log Depth Circuits for Division and Related Problems

DOI10.1137/0215070zbMath0619.68047OpenAlexW2003519998MaRDI QIDQ3756526

H. James Hoover, P. W. Beame, Stephen A. Cook

Publication date: 1986

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

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

zbMATH Keywords

algorithmdivisibilitycircuit complexitymultiple productsspace complexitycircuit depthinteger divisionpoweringdepth complexityoptimal depth Boolean ciruits

Mathematics Subject Classification ID

Related Items (60)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Sieve algorithms for perfect power testing ⋮ Threshold circuits of bounded depth ⋮ On small depth threshold circuits ⋮ Inversion in finite fields using logarithmic depth ⋮ On the parallel complexity of linear groups ⋮ Boolean circuits versus arithmetic circuits ⋮ On design of circuits of logarithmic depth for inversion in finite fields ⋮ On uniformity within \(NC^ 1\) ⋮ Ranking and formal power series ⋮ Iterated multiplication in \(VTC^0\) ⋮ Expressing uniformity via oracles ⋮ Efficient parallel circuits and algorithms for division ⋮ Skew circuits of small width ⋮ Complexity of computation in finite fields ⋮ Extensions of an idea of McNaughton ⋮ On parallel complexity of analytic functions ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ The random oracle model: a twenty-year retrospective ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Secure collaborative supply chain planning and inverse optimization -- the JELS model ⋮ Counting problems and algebraic formal power series in noncommuting variables ⋮ Ring-based identity based encryption -- asymptotically shorter MPK and tighter security ⋮ Direct computation of branching programs and its applications to more efficient lattice-based cryptography ⋮ Parallel models of computation: An introductory survey ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting) ⋮ Highly parallel computations modulo a number having only small prime factors ⋮ An arithmetic model of computation equivalent to threshold circuits ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ On iterated integer product ⋮ Root finding with threshold circuits ⋮ Efficient CRT-based residue-to-binary converter for the arbitrary moduli set ⋮ A parametric error analysis of Goldschmidt's division algorithm ⋮ Division in logspace-uniformNC¹ ⋮ Unnamed Item ⋮ Fast arithmetics using Chinese remaindering ⋮ A randomized sublinear time parallel GCD algorithm for the EREW PRAM ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Symmetries and the complexity of pure Nash equilibrium ⋮ Space complexity of abelian groups ⋮ Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families ⋮ Compact designated verifier NIZKs from the CDH assumption without pairings ⋮ Effective entropies and data compression ⋮ Threshold circuits of small majority-depth ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Polynomial time relatively computable triangular arrays for almost sure convergence ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Modular exponentiation via the explicit Chinese remainder theorem ⋮ Unnamed Item ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Efficient threshold circuits for power series ⋮ Computing a context-free grammar-generating series ⋮ A div(n) depth Boolean circuit for smooth modular inverse ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

This page was built for publication: Log Depth Circuits for Division and Related Problems