Removing Ramsey theory: Lower bounds with smaller domain size
From MaRDI portal
Publication:1392014
DOI10.1016/S0304-3975(96)00020-5zbMath0911.68015MaRDI QIDQ1392014
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00020-5
68M99: Computer system organization
Cites Work
- Simulations among concurrent-write PRAMs
- Parallel computation and conflicts in memory access
- Processor-time tradeoffs in PRAM simulations
- On the Size of Separating Systems and Families of Perfect Hash Functions
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Relations between Concurrent-Write Models of Parallel Computation
- The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$