Optimal bounds for decision problems on the CRCW PRAM

DOI10.1145/65950.65958MaRDI QIDQ4710686zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(49)

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

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)