research
∙
11/08/2022
Universal Sorting: Finding a DAG using Priced Comparisons
We resolve two open problems in sorting with priced information, introdu...
share
research
∙
01/30/2021
Fragile Complexity of Adaptive Algorithms
The fragile complexity of a comparison-based algorithm is f(n) if each i...
research
∙
02/12/2020
On the I/O complexity of the k-nearest neighbor problem
We consider static, external memory indexes for exact and approximate ve...
research
∙
03/07/2019
External memory priority queues with decrease-key and applications to graph algorithms
We present priority queues in the external memory model with block size ...
research
∙
02/28/2019
Dynamic Planar Convex Hull
In this article, we determine the amortized computational complexity of ...
research
∙
01/09/2019
Fragile Complexity of Comparison-Based Algorithms
We initiate a study of algorithms with a focus on the computational comp...
research
∙
10/24/2018