Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

DOI10.1137/0215006zbMath0591.68049OpenAlexW2070570981MaRDI QIDQ3719831

Cynthia Dwork, Stephen A. Cook, K. Ruediger Reischuk

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215006

zbMATH Keywords

sortingparallel computationtime lower boundssynchronous parallel computer

Mathematics Subject Classification ID

Related Items (87)

Exact lower time bounds for computing Boolean functions on CREW PRAMs ⋮ On the long-run sensitivity of probabilistic Boolean networks ⋮ Unbounded fan-in circuits and associative functions ⋮ Fast integer merging on the EREW PRAM ⋮ An insight on PRAM computational bounds ⋮ Time bounds on synchronization in a periodic distributed system ⋮ An optimal EREW PRAM algorithm for minimum spanning tree verification ⋮ Pseudo-average block sensitivity equals average sensitivity ⋮ Gossiping and broadcasting versus computing functions in networks ⋮ Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions ⋮ Parallel integer sorting using small operations ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Retrieval of scattered information by EREW, CREW and CRCW PRAMs ⋮ Sensitivity vs. block sensitivity of Boolean functions ⋮ The parallel complexity of integer prefix summation ⋮ Distributed sorting algorithms for multi-channel broadcast networks ⋮ On the time required to sum n semigroup elements on a parallel machine with simultaneous writes ⋮ A time-optimal parallel algorithm for three-dimensional convex hulls ⋮ Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM ⋮ Limits on the power of concurrent-write parallel machines ⋮ Tight Bounds for Asynchronous Renaming ⋮ Retrieval of scattered information by EREW, CREW, and CRCW PRAMs ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ Time-optimal tree computations on sparse meshes ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ Parallélisation d'algorithmes avec un nombre fixe de processeurs ⋮ On separating the EREW and CREW PRAM models ⋮ Concurrent counting is harder than queuing ⋮ ERCW PRAMs and optical communication ⋮ Boolean nested canalizing functions: a comprehensive analysis ⋮ On the performance of networks with multiple busses ⋮ Optimal parallel algorithms for proximate points, with applications ⋮ Removing Ramsey theory: Lower bounds with smaller domain size ⋮ The influence of canalization on the robustness of Boolean networks ⋮ A time-optimal solution for the path cover problem on cographs. ⋮ Collectively canalizing Boolean functions ⋮ Minterm-transitive functions with asymptotically smallest block sensitivity ⋮ Efficient simulation of circuits by EREW PRAMs ⋮ Fast integer merging on the EREW PRAM ⋮ On the resolution of the sensitivity conjecture ⋮ A complexity theory of efficient parallel algorithms ⋮ Incomparability in parallel computation ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ Gossiping and broadcasting versus computing functions in networks. ⋮ Hundreds of impossibility results for distributed computing ⋮ Finding a minimal cover for binary images: An optimal parallel algorithm ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ On the message complexity of binary Byzantine agreement under crash failures ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Sorting on PRAMs with reconfigurable buses ⋮ PRAMs with variable word-size ⋮ Time-optimal tree computations on sparse meshes ⋮ The computational complexity of universal hashing ⋮ Matching parentheses in parallel ⋮ An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ An improved lower bound on the sensitivity complexity of graph properties ⋮ Maximal sensitivity of Boolean nested canalizing functions ⋮ Laced Boolean functions and subset sum problems in finite fields ⋮ Block sensitivity of minterm-transitive functions ⋮ Properties of complexity measures for PRAMs and WRAMs ⋮ Ordered vertex removal and subgraph problems ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Parallel algorithms for red--black trees ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ New bounds for energy complexity of Boolean functions ⋮ More Efficient Parallel Integer Sorting ⋮ Message lower bounds via efficient network synchronization ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree ⋮ Optimal parallel two dimensional text searching on a CREW PRAM ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Parallel random access machines with bounded memory wordsize ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms ⋮ Certificate complexity of elementary symmetric Boolean functions ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ Complexity measures and decision tree complexity: a survey. ⋮ Restricted CRCW PRAMs ⋮ Improving the efficiency of parallel minimum spanning tree algorithms ⋮ Large parallel machines can be extremely slow for small problems ⋮ Certificate complexity and symmetry of nested canalizing functions ⋮ Selecting small ranks in EREW PRAM

This page was built for publication: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes