Towards a complexity theory of synchronous parallel computation

Cited in

(28)

Speedups of deterministic machines by synchronous parallel machines
An introduction to parallelism in combinatorial optimization
Fast parallel absolute irreducibility testing
Routing, merging, and sorting on parallel models of computation
Array processing machines: an abstract model
On nondeterminism in parallel computation
A note on strategy elimination in bimatrix games
Parallel algorithms for solvable permutation groups
Complexity theory of parallel time and hardware
The complexity of computing the number of strings of given length in context-free languages
Oracle branching programs and Logspace versus \(P^*\)
Expected parallel time and sequential space complexity of graph and digraph problems
Efficient algorithms for parallel sorting on mesh multicomputers
Parallel evaluation of arithmetic circuits
Finding optimal subgraphs by local search
Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
Data independence of read, write, and control structures in PRAM computations
The complexity of graph languages generated by hyperedge replacement
Parallel pointer machines
Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
Graph layout problems
Weak parallel machines: a new class of physically feasible parallel machine models
On languages accepted with simultaneous complexity bounds and their ranking problem
Subset mapping problems in solvable automata
The 1982 ACM Turing Award lecture. An overview of computational complexity
A complexity theory of efficient parallel algorithms
Parallel models of computation: An introductory survey

This page was built for publication: Towards a complexity theory of synchronous parallel computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1158753)