Uniform constant-depth threshold circuits for division and iterated multiplication.
type: Item
instance of: scholarly article
title: Uniform constant-depth threshold circuits for division and iterated multiplication.
zbMATH Open document ID: 1059.68044
DOI: 10.1016/S0022-0000(02)00025-9
author: William Hesse
author: Eric Allender
author: David A. Mix Barrington
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1910857
zbMATH Keywords: division
zbMATH Keywords: iterated multiplication
zbMATH Keywords: uniform threshold circuits
zbMATH Keywords: circuit complexity
zbMATH Keywords: Chinese remainder representation
zbMATH Keywords: computation in abelian groups
Wikidata QID: Q29306000
MaRDI profile type: Publication
cites work: On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
cites work: Reducing the complexity of reductions
cites work: The division breakthroughs
cites work: Q4938621
cites work: Rudimentary reductions revisited
cites work: Q4287355
cites work: Isolation, matching, and counting uniform and nonuniform upper bounds
cites work: Q4218115
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: On the complexity of some problems on groups input as multiplication tables
cites work: Log Depth Circuits for Division and Related Problems
cites work: Nondeterministic \(NC^1\) computation
cites work: Constant Depth Reducibility
cites work: Division in logspace-uniform NC
cites work: Q4062633
cites work: Inductive counting for width-restricted branching programs
cites work: Fast Parallel Arithmetic via Modular Representation
cites work: Definability by constant-depth polynomial-size circuits
cites work: Bits and relative order from residues, space efficiently
cites work: Very Fast Parallel Polynomial Arithmetic
cites work: Logarithmic Depth Circuits for Hermite Interpolation
cites work: Bounded-depth, polynomial-size circuits for symmetric functions
cites work: Time-space tradeoffs for satisfiability
cites work: On tape bounds for single letter alphabet language processing
cites work: Q3975135
cites work: Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
cites work: Q4535013
cites work: Q4227581
cites work: The complexity of iterated multiplication
cites work: Q4359462
cites work: Space-Efficient Deterministic Simulation of Probabilistic Automata
cites work: Threshold circuits of small majority-depth
cites work: Efficient threshold circuits for power series
cites work: Q5628106
cites work: Q3999199
cites work: Logarithmic Depth Circuits for Algebraic Functions
cites work: On Threshold Circuits and Polynomial Computation
cites work: Optimal Size Integer Division Circuits
cites work: On uniform circuit complexity
cites work: Efficient parallel circuits and algorithms for division
cites work: On Optimal Depth Threshold Circuits for Multiplication and Related Problems
cites work: If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n
cites work: Turing machines with sublogarithmic space
cites work: On the Decomposability of $NC$ and $AC$
DBLP publication ID: journals/jcss/HesseAB02
description: scientific article; zbMATH DE number 1910857