Removing Ramsey theory: Lower bounds with smaller domain size

DOI10.1016/S0304-3975(96)00020-5zbMath0911.68015OpenAlexW1963677148MaRDI QIDQ1392014

Jeff Edmonds

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

zbMATH Keywords

Ramsey theory

Mathematics Subject Classification ID

Computer system organization (68M99)

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} )$

This page was built for publication: Removing Ramsey theory: Lower bounds with smaller domain size