Simulation of Parallel Random Access Machines by Circuits
From MaRDI portal
Recommendations
- Parallelism in random access machines
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Limits on the power of concurrent-write parallel machines
- Parallel random access machines with bounded memory wordsize
Cited in
(70)- Array processing machines: an abstract model
- Limits on the power of concurrent-write parallel machines
- Parallel complexity of logical query programs
- 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
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- The bulk-synchronous parallel random access machine
- The complexity of short two-person games
- Properties that characterize LOGCFL
- Arithmetizing uniform NC
- Learning 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
- Tight complexity bounds for term matching problems
- Two \(P\)-complete problems in the theory of the reals
- Unambiguity of circuits
- On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
- Feasible real random access machines
- Restricted CRCW PRAMs
- A query language for NC
- Faster optimal parallel prefix sums and list ranking
- Separating NC along the \(\delta\) axis
- The size and depth of layered Boolean circuits
- Data independence of read, write, and control structures in PRAM computations
- Thresholds for extreme orientability
- Parallel pointer machines
- Parallelizing time with polynomial circuits
- On uniformity within \(NC^ 1\)
- Simulation of PRAMs with scan primitives by unbounded fan-in circuits
- The complexity of ranking simple languages
- On the power of families of recognizer spiking neural P systems
- Modular exponentiation via the explicit Chinese remainder theorem
- Extensions of an idea of McNaughton
- Collapsing the hierarchy of parallel computational models
- scientific article; zbMATH DE number 3898252 (Why is no real title available?)
- On similarity and duality of computation (I)
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- scientific article; zbMATH DE number 3986645 (Why is no real title available?)
- Parallel complexity of algebraic operations
- scientific article; zbMATH DE number 408789 (Why is no real title available?)
- Parallelism Always Helps
- Faster all-pairs shortest paths via circuit complexity
- From circuit complexity to faster all-pairs shortest paths
- Graph layout problems
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Computation models and function algebras
- Lowerbounds for Bisimulation by Partition Refinement
- Advocating ownership
- Imperative process algebra and models of parallel computation
- Time lower bounds do not exist for CRCW PRAMs
- Using maximal independent sets to solve problems in parallel
- On the formalization of the notion of a concurrent algorithm
- An NC algorithm for recognizing tree adjoining languages
- An evaluation of massively parallel algorithms for DFA minimization
- Evaluating monotone circuits on surfaces
- Parallel random access machines with bounded memory wordsize
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- An optimal parallel connectivity algorithm
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
- Large parallel machines can be extremely slow for small problems
- The parallel complexity of two problems on concurrency
- Algorithmic analysis of priority-based bin packing
- 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
- Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
This page was built for publication: Simulation of Parallel Random Access Machines by Circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3316595)
