Optimal bounds for decision problems on the CRCW PRAM
From MaRDI portal
Publication:4710686
DOI10.1145/65950.65958zbMath0825.68378OpenAlexW1992470151WikidataQ56959226 ScholiaQ56959226MaRDI QIDQ4710686
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
Related Items
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, 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, 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
