Transforming comparison model lower bounds to the parallel-random-access-machine
From MaRDI portal
Publication:287050
DOI10.1016/S0020-0190(97)00032-XzbMath1337.68113OpenAlexW2039192511MaRDI QIDQ287050
Dany Breslauer, Friedhelm Meyer auf der Heide, Devdatt P. Dubhashi, 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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- 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
- 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
- Parallelism in Comparison Problems
- 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
This page was built for publication: Transforming comparison model lower bounds to the parallel-random-access-machine
