5 citations · 14 across the 8 of their papers we have counts for
11 papers
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
Mayank Goswami, Riko Jacob
We generalize the classical nuts and bolts problem to a setting where the input is a collection of nuts and bolts, and there is no promise of any matching pairs. It is not…
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…
Dynamic Planar Convex Hull
Riko Jacob, Gerth Stølting Brodal
In this article, we determine the amortized computational complexity of the planar dynamic convex hull problem by querying. We present a data structure that maintains a set of n po…
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…
Charting the Complexity Landscape of Waypoint Routing
Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Riko Jacob +1
Modern computer networks support interesting new routing models in which traffic flows from a source s to a destination t can be flexibly steered through a sequence of waypoints, s…
On the Complexity of List Ranking in the Parallel External Memory Model
Riko Jacob, Tobias Lieber, Nodari Sitchinava
We study the problem of list ranking in the parallel external memory (PEM) model. We observe an interesting dual nature for the hardness of the problem due to limited information e…
Tight Bounds for Low Dimensional Star Stencils in the Parallel External Memory Model
Philipp Hupp, Riko Jacob
Stencil computations on low dimensional grids are kernels of many scientific applications including finite difference methods used to solve partial differential equations. On typic…
The Efficiency of MapReduce in Parallel External Memory
Gero Greiner, Riko Jacob
Since its introduction in 2004, the MapReduce framework has become one of the standard approaches in massive distributed and parallel computation. In contrast to its intensive use…