Optimal bounds for decision problems on the CRCW PRAM

DOI10.1145/65950.65958zbMath0825.68378OpenAlexW1992470151WikidataQ56959226 ScholiaQ56959226MaRDI QIDQ4710686

P. W. Beame, Johan T. Håstad

Publication date: 25 June 1992

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/65950.65958

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel numerical computation (65Y05)

Related Items (45)

Coloring permutation graphs in parallel ⋮ Designing algorithms by expectations ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Simulation of PRAMs with scan primitives by unbounded fan-in circuits ⋮ Sorting and searching revisted ⋮ Constant-time parallel recognition of split graphs ⋮ The parallel complexity of integer prefix summation ⋮ SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ MATRIX OPERATIONS USING ARRAYS WITH RECONFIGURABLE OPTICAL BUSES∗ ⋮ PARALLEL BLOCK-FINDING USING DISTANCE MATRICES ⋮ Designing checkers for programs that run in parallel ⋮ The complexity of parallel prefix problems on small domains ⋮ An exponential separation between the parity principle and the pigeonhole principle ⋮ Integer summing algorithms on reconfigurable meshes ⋮ The queue-read queue-write asynchronous PRAM model ⋮ On the Parallel Evaluation of Dwba Integrals ⋮ Fast parallel Lyndon factorization with applications ⋮ A sublogarithmic convex hull algorithm ⋮ INTEGER SORTING AND ROUTING IN ARRAYS WITH RECONFIGURABLE OPTICAL BUSES ⋮ Lower bounds for recognizing small cliques on CRCW PRAM's ⋮ Incomparability in parallel computation ⋮ Round Compression for Parallel Matching Algorithms ⋮ Improved deterministic parallel integer sorting ⋮ Time lower bounds do not exist for CRCW PRAMs ⋮ Efficient parallel algorithms can be made robust ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ On a compaction theorem of Ragde ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Sorting on PRAMs with reconfigurable buses ⋮ Exponential lower bounds for the pigeonhole principle ⋮ Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes ⋮ Matching parentheses in parallel ⋮ More efficient parallel flow algorithms ⋮ Unnamed Item ⋮ Integer priority queues with decrease key in constant time and the single source shortest paths problem ⋮ Optimal parallel algorithms for periods, palindromes and squares ⋮ Limitations of the QRQW and EREW PRAM models ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ Sorting in linear time? ⋮ Scalable algorithms for the mesh with buses: merging, sorting and selection ⋮ Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space ⋮ ON THE POWER OF SOME PRAM MODELS

This page was built for publication: Optimal bounds for decision problems on the CRCW PRAM