The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
- 1 August 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (3) , 399-410
- https://doi.org/10.1137/0401040
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- Simulations among concurrent-write PRAMsAlgorithmica, 1988
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous WritesSIAM Journal on Computing, 1986
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- Parallel computation and conflicts in memory accessInformation Processing Letters, 1982
- An information-theoretic method in combinatorial theoryJournal of Combinatorial Theory, Series A, 1977
- Combinatorial Theorems on Classifications of Subsets of a Given SetProceedings of the London Mathematical Society, 1952
- A Combinatorial TheoremJournal of the London Mathematical Society, 1950