Removing Ramsey theory: Lower bounds with smaller domain size
From MaRDI portal
Publication:1392014
DOI10.1016/S0304-3975(96)00020-5zbMATH Open0911.68015OpenAlexW1963677148MaRDI QIDQ1392014FDOQ1392014
Authors: 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
Recommendations
- New lower bounds for parallel computation
- Transforming comparison model lower bounds to the parallel-random-access-machine
- Applications of Ramsey's theorem to decision tree complexity
- On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
- The Complexity of Parallel Sorting
Cites Work
- On the Size of Separating Systems and Families of Perfect Hash Functions
- Parallel computation and conflicts in memory access
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- The Parallel Complexity of Element Distinctness is $\Omega ( \sqrt{\log n} )$
- Simulations among concurrent-write PRAMs
- Relations between Concurrent-Write Models of Parallel Computation
- Processor-time tradeoffs in PRAM simulations
This page was built for publication: Removing Ramsey theory: Lower bounds with smaller domain size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392014)
