Selected papers that cite this one
- Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 427-436, Las Vegas, Nevada, 29 May-1 June 1995.
- Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. Sorting in linear time? Journal of Computer and System Sciences, 57(1):74-93, August 1998.
- Alberto Apostolico and Dany Breslauer. An optimal O(log log n)-time parallel algorithm for detecting all squares in a string. SIAM Journal on Computing, 25(6):1318-1331, December 1996.
- A. Apostolico and M. Crochemore. Fast parallel Lyndon factorization with applications. Mathematical Systems Theory, 28(2):89-108, March/April 1995.
- Hannah Bast and Torben Hagerup. Fast parallel space allocation, estimation and integer sorting. Information and Computation, 123(1):72-110, 15 November 1995.
- Paul Beame and Toniann Pitassi. An exponential separation between the parity principle and the pigeonhole principle. Annals of Pure and Applied Logic, 80(3):195-228, 26 August 1996.
- P. C. P. Bhatt, K. Diks, T. Hagerup, V. C. Prasad, T. Radzik, and S. Saxena. Improved deterministic parallel integer sorting. Information and Computation, 94(1):29-47, September 1991.
- Dany Breslauer, Artur Czumaj, Devdatt P. Dubhashi, and Friedhelm Meyer auf der Heide. Transforming comparison model lower bounds to the parallel-random-access-machine. Information Processing Letters, 62(2):103-110, 28 April 1997.
- Shiva Chaudhuri. Sensitive functions and approximate problems. In 34th Annual Symposium on Foundations of Computer Science, pages 186-193, Palo Alto, California, 3-5 November 1993. IEEE.
- Shiva Chaudhuri. Sensitive functions and approximate problems. Information and Computation, 126(2):161-168, 1 May 1996.
- Shiva P. Chaudhuri and Jaikumar Radhakrishnan. The complexity of parallel prefix problems on small domains. Information and Computation, 138(1):1-22, 10 October 1997.
- Lin Chen. Optimal circular arc representations: Properties, recognition, and construction. Journal of Computer and System Sciences, 56(3):320-331, April 1998.
- Shenfeng Chen and John H. Reif. Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs. In 34th Annual Symposium on Foundations of Computer Science, pages 104-112, Palo Alto, California, 3-5 November 1993. IEEE.
- Anne Condon, Richard Ladner, Jordan Lampe, and Rakesh Sinha. Complexity of sub-bus mesh computations. SIAM Journal on Computing, 25(3):520-539, June 1996.
- Martin Dietzfelbinger, Miros{\l}aw Kuty{\l}owski, and Rüdiger Reischuk. Feasible time-optimal algorithms for Boolean functions on exclusive-write parallel random-access machines. SIAM Journal on Computing, 25(6):1196-1230, December 1996.
- P. B. Gibbons, Y. Matias, and V. Ramachandran. The queue-read queue-write asynchronous PRAM model. Theoretical Computer Science, 196(1-2):3-29, 6 April 1998.
- Joseph Gil and Yossi Matias. Simple fast parallel hashing by oblivious execution. SIAM Journal on Computing, 27(5):1348-1375, October 1998.
- Torben Hagerup. Fast deterministic processor allocation. Journal of Algorithms, 18(3):629-649, May 1995.
- Torben Hagerup. Optimal parallel string algorithms: Merging, sorting and computing the minimum. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 382-391, Montréal, Québec, Canada, 23-25 May 1994.
- Torben Hagerup. The parallel complexity of integer prefix summation. Information Processing Letters, 56(1):59-64, 13 October 1995.
- Kazuo Iwama, Chuzo Iwamoto, and Manzur Morshed. Time lower bounds do not exist for CRCW PRAMs. Theoretical Computer Science, 155(2):411-424, 11 March 1996.
- Philip D. MacKenzie. The random adversary: A lower-bound technique for randomized parallel algorithms. SIAM Journal on Computing, 26(6):1559-1580, December 1997.
- Philip D. MacKenzie and Quentin F. Stout. Ultrafast expected time parallel algorithms. Journal of Algorithms, 26(1):1-33, January 1998.
- Koji Nakano and Koichi Wada. Integer summing algorithms on reconfigurable meshes. Theoretical Computer Science, 197(1-2):57-77, 15 May 1998.
- Stavros D. Nikolopoulos. Constant-time parallel recognition of split graphs. Information Processing Letters, 54(1):1-8, 14 April 1995.
- R. Rubinfeld. Designing checkers for programs that run in parallel. Algorithmica, 15(4):287-301, April 1996.
- R. Sarnath and Xin He. On parallel selection and searching in partial orders: Sorted matrices. Journal of Parallel and Distributed Computing, 40(2):242-247, 1 February 1997.
- Mikkel Thorup. Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 352-359, New Orleans, Louisiana, 5-7 January 1997.
- Jerry L. Trahan, Ramachandran Vaidyanathan, and Ratnapuri K. Thiruchelvan. On the power of segmenting and fusing buses. Journal of Parallel and Distributed Computing, 34(1):82-94, 10 April 1996.