The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$

DOI10.1137/0401040zbMath0655.68042OpenAlexW38294843MaRDI QIDQ3802607

Avi Wigderson, William Steiger, Endre Szemerédi, Prabhakar Ragde

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401040

zbMATH Keywords

lower boundPRAMparallel random access machinesmodel of parallel computationelement distinctness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ Simulations among concurrent-write PRAMs ⋮ Removing Ramsey theory: Lower bounds with smaller domain size ⋮ Processor-time tradeoffs in PRAM simulations ⋮ On the power of concurrent-write PRAMs with read-only memory ⋮ Large parallel machines can be extremely slow for small problems