Transforming comparison model lower bounds to the parallel-random-access-machine

DOI10.1016/S0020-0190(97)00032-XzbMATH Open1337.68113OpenAlexW2039192511MaRDI QIDQ287050FDOQ287050

Authors: Dany Breslauer, Devdatt P. Dubhashi, Friedhelm Meyer auf der Heide, Artur Czumaj 

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00032-x

Recommendations

• New lower bounds for parallel computation
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Incomparability in parallel computation
• Lower bounds for randomized exclusive write PRAMs
• The Complexity of Parallel Sorting

zbMATH Keywords

lower boundsRamsey theorycomparison modelPRAM model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• Title not available (Why is that?)
• Parallelism in Comparison Problems
• Routing, merging, and sorting on parallel models of computation
• Optimal parallel selection has complexity O(log log N)
• Finding all periods and initial palindromes of a string in parallel
• Applications of Ramsey's theorem to decision tree complexity
• The Complexity of Parallel Sorting
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
• Finding an Approximate Maximum
• Finding the maximum, merging, and sorting in a parallel computation model
• A Lower Bound for Parallel String Matching
• Optimal bounds for decision problems on the CRCW PRAM
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
• A Combinatorial Theorem
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Parallel comparison algorithms for approximation problems
• Parallel selection
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm

Cited In (2)

• Towards optimal packed string matching
• On the strength of comparisons in property testing

This page was built for publication: Transforming comparison model lower bounds to the parallel-random-access-machine

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