Transforming comparison model lower bounds to the parallel-random-access-machine (Q287050): Difference between revisions

@@ Property / author @@
-Artur Czumaj
@@ Property / author: Artur Czumaj / rank @@
-Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal parallel selection has complexity O(log log N)
+Normal rank
@@ Property / cites work @@
+Finding an Approximate Maximum
@@ Property / cites work: Finding an Approximate Maximum / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel comparison algorithms for approximation problems
+Normal rank
@@ Property / cites work @@
+An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
+Normal rank
@@ Property / cites work @@
+Parallel selection
@@ Property / cites work: Parallel selection / rank @@
+Normal rank
@@ Property / cites work @@
+Tight Comparison Bounds on the Complexity of Parallel Sorting
+Normal rank
@@ Property / cites work @@
+Optimal bounds for decision problems on the CRCW PRAM
+Normal rank
@@ Property / cites work @@
+Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
+Normal rank
@@ Property / cites work @@
+Routing, merging, and sorting on parallel models of computation
+Normal rank
@@ Property / cites work @@
+A Lower Bound for Parallel String Matching
@@ Property / cites work: A Lower Bound for Parallel String Matching / rank @@
+Normal rank
@@ Property / cites work @@
+Finding all periods and initial palindromes of a string in parallel
+Normal rank
@@ Property / cites work @@
+A Combinatorial Theorem
@@ Property / cites work: A Combinatorial Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial Theorems on Classifications of Subsets of a Given Set
+Normal rank
@@ Property / cites work @@
+Q3997075
@@ Property / cites work: Q3997075 / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Parallel Sorting
@@ Property / cites work: The Complexity of Parallel Sorting / rank @@
+Normal rank
@@ Property / cites work @@
+Applications of Ramsey's theorem to decision tree complexity
+Normal rank
@@ Property / cites work @@
+The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
+Normal rank
@@ Property / cites work @@
+Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
+Normal rank
@@ Property / cites work @@
+Finding the maximum, merging, and sorting in a parallel computation model
+Normal rank
@@ Property / cites work @@
+Parallelism in Comparison Problems
@@ Property / cites work: Parallelism in Comparison Problems / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0020-0190(97)00032-x
+Normal rank
@@ Property / OpenAlex ID @@
+W2039192511
@@ Property / OpenAlex ID: W2039192511 / rank @@
+Normal rank