Unbounded fan-in circuits and associative functions
The computation of finite semigroups using unbounded fan-in circuits is considered. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size \(O(nf^{-1}(n))\) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.
- A unified approach to models of synchronous parallel machines
- Finding the maximum, merging, and sorting in a parallel computation model
- scientific article; zbMATH DE number 3852437 (Why is no real title available?)
- scientific article; zbMATH DE number 3492136 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Implementation of simultaneous memory address access in models that forbid it
- Parallel Prefix Computation
- Parity, circuits, and the polynomial-time hierarchy
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Linear-size constant-depth polylog-threshold circuits
- Regular languages in \(NC\)
- Multiplication, division, and shift instructions in parallel random access machines
- The complexity of parallel prefix problems on small domains
- Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\)
- Designing checkers for programs that run in parallel
- Space complexity of reachability testing in labelled graphs
- Steiner transitive-closure spanners of low-dimensional posets
- Collapse of the hierarchy of constant-depth exact quantum circuits
- Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size
- Steiner transitive-closure spanners of low-dimensional posets
- Parallel complexity of algebraic operations
- Faster all-pairs shortest paths via circuit complexity
- From circuit complexity to faster all-pairs shortest paths
- Space Complexity of Reachability Testing in Labelled Graphs
- An improved parallel algorithm for integer GCD
- Circuit complexity of regular languages
- Circuit complexity of regular languages
- Prefix graphs and their applications
- Unary and two-variable interval logics
- High girth augmented trees are huge
This page was built for publication: Unbounded fan-in circuits and associative functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083202)
