2 citations · 2 across the 1 of their papers we have counts for
5 papers · 1 filter
Fragile Complexity of Adaptive Algorithms
Prosenjit Bose, Pilar Cano, Rolf Fagerberg +3
The fragile complexity of a comparison-based algorithm is if each input element participates in comparisons. In this paper, we explore the fragile complexity of al…
On the I/O complexity of the k-nearest neighbor problem
Mayank Goswami, Riko Jacob, Rasmus Pagh
We consider static, external memory indexes for exact and approximate versions of the -nearest neighbor (-NN) problem, and show new lower bounds under a standard indivisibili…
Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms
John Iacono, Riko Jacob, Konstantinos Tsakalidis
We present priority queues in the cache-oblivious external memory model with block size and main memory size that support on elements, operation \textsc{UPDATE} (combin…
Fragile Complexity of Comparison-Based Algorithms
Peyman Afshani, Rolf Fagerberg, David Hammer +5
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the ma…
Lower Bounds for Oblivious Data Structures
Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen
An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced b…