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

DOI10.1016/S0020-0190(97)00032-XMaRDI QIDQ287050zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)