2 citations · 5 across the 5 of their papers we have counts for
6 papers
A Tight Lower Bound for Decrease-Key in the Pure Heap Model
John Iacono, Özgür Özkan
We improve the lower bound on the amortized cost of the decrease-key operation in the pure heap model and show that any pure-heap-model heap (that has a \bigoh{\log n} amortized-ti…
Cache-Oblivious Persistence
Pooya Davoodi, Jeremy T. Fineman, John Iacono +1
Partial persistence is a general transformation that takes a data structure and allows queries to be executed on any past state of the structure. The cache-oblivious model is the l…
The Complexity of Order Type Isomorphism
Greg Aloupis, John Iacono, Stefan Langerman +1
The order type of a point set in maps each -tuple of points to its orientation (e.g., clockwise or counterclockwise in ). Two point sets and have the sa…
Why some heaps support constant-amortized-time decrease-key operations, and others do not
John Iacono
A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend Omega(log log n / log log log n) amortized time on th…
Max-Throughput for (Conservative) k-of-n Testing
Lisa Hellerstein, Özgür Özkan, Linda Sellie
We define a variant of k-of-n testing that we call conservative k-of-n testing. We present a polynomial-time, combinatorial algorithm for the problem of maximizing throughput of co…
Mergeable Dictionaries
John Iacono, Özgür Özkan
A data structure is presented for the Mergeable Dictionary abstract data type, which supports the following operations on a collection of disjoint sets of totally ordered data: Pre…