Simulation of Parallel Random Access Machines by Circuits
From MaRDI portal
Publication:3316595
DOI10.1137/0213027zbMath0533.68048OpenAlexW1967575173MaRDI QIDQ3316595
Uzi Vishkin, Larry J. Stockmeyer
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213027
circuit complexitycomplexity measurescomputational powercombinational circuitsalternating Turing machinesparallel RAMparallel time complexitysynchronous parallelism
Related Items (55)
Parallel pointer machines ⋮ On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions ⋮ Algorithmic analysis of priority-based bin packing ⋮ Simulation of PRAMs with scan primitives by unbounded fan-in circuits ⋮ Array processing machines: an abstract model ⋮ On uniformity within \(NC^ 1\) ⋮ Limits on the power of concurrent-write parallel machines ⋮ Parallel complexity of logical query programs ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Lower bound arguments with ``inaccessible numbers ⋮ Parallel computation with threshold functions ⋮ A parallelizable lexicographically first maximal edge-induced subgraph problem ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ Parallel complexity of algebraic operations ⋮ A query language for NC ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ Extensions of an idea of McNaughton ⋮ Graph layout problems ⋮ Computation models and function algebras ⋮ Lowerbounds for Bisimulation by Partition Refinement ⋮ The size and depth of layered Boolean circuits ⋮ Parallelizing time with polynomial circuits ⋮ Efficient simulation of circuits by EREW PRAMs ⋮ Parallel models of computation: An introductory survey ⋮ Lower bounds for recognizing small cliques on CRCW PRAM's ⋮ Subtree isomorphism is in random NC ⋮ The complexity of short two-person games ⋮ Properties that characterize LOGCFL ⋮ Arithmetizing uniform \(NC\) ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Learning in parallel ⋮ Time lower bounds do not exist for CRCW PRAMs ⋮ Using maximal independent sets to solve problems in parallel ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ COLLAPSING THE HIERARCHY OF PARALLEL COMPUTATIONAL MODELS ⋮ Thresholds for extreme orientability ⋮ Tight complexity bounds for term matching problems ⋮ Two \(P\)-complete problems in the theory of the reals ⋮ Unambiguity of circuits ⋮ The complexity of ranking simple languages ⋮ Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs ⋮ ON THE POWER OF FAMILIES OF RECOGNIZER SPIKING NEURAL P SYSTEMS ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Parallel random access machines with bounded memory wordsize ⋮ Faster optimal parallel prefix sums and list ranking ⋮ Separating NC along the \(\delta\) axis ⋮ Modular exponentiation via the explicit Chinese remainder theorem ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ An optimal parallel connectivity algorithm ⋮ Restricted CRCW PRAMs ⋮ Large parallel machines can be extremely slow for small problems ⋮ The parallel complexity of two problems on concurrency
This page was built for publication: Simulation of Parallel Random Access Machines by Circuits
