Optimal bounds for decision problems on the CRCW PRAM

DOI10.1145/65950.65958zbMATH Open0825.68378OpenAlexW1992470151WikidataQ56959226 ScholiaQ56959226MaRDI QIDQ4710686FDOQ4710686

Authors: Paul Beame, Johan Hastad 

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

Recommendations

• Time lower bounds do not exist for CRCW PRAMs
• New lower bounds for parallel computation
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Exact lower time bounds for computing Boolean functions on CREW PRAMs

Mathematics Subject Classification ID

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

Cited In (49)

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

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

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