Lower Bounds for Sorting with Few Random Accesses to External Memory Martin Grohe   View Paper (PDF)   Return to Research Session 6: Complexity and Performance Evaluation / Data Stream Abstract ARB system for answering XPath queries is based on such a strategy. In this model, we prove lower bounds for sorting the input data. As opposed to related results for models without auxiliary external memory for intermediate results, we cannot rely on communication complexity to establish these lower bounds. Instead, we simulate our model by a non-uniform computation model for which we can establish the lower bounds by combinatorial means. ©2006 Association for Computing Machinery