John Iacono

Bernhard Haeupler, Richard Hladík, John Iacono et al.

We consider the problem of sorting $n$ items, given the outcomes of $m$ pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T)$ time and does $O(\log T)$ comparisons, where $T$ is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $O(\log T)$ on the number of comparisons has a time bound of $O(n^{2.5})$ and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-$k$ sorting problem: Given $k$ and the outcomes of some pre-existing comparisons, output the smallest $k$ items in sorted order. The modified algorithm solves the top-$k$ sorting problem in minimum time and comparisons, to within constant factors.

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung et al.

Let $S$ be a set of $n$ points in $\mathbb{R}^d$, where $d \geq 2$ is a constant, and let $H_1,H_2,\ldots,H_{m+1}$ be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly $n/m$ points of $S$ are between any two successive hyperplanes. Let $A(S,m)$ be the set of different closest pairs in the ${{m+1} \choose 2}$ vertical slabs that are bounded by $H_i$ and $H_j$, over all $1 \leq i < j \leq m+1$. We prove tight bounds for the largest possible size of $A(S,m)$, over all point sets of size $n$, and for all values of $1 \leq m \leq n$. As a result of these bounds, we obtain, for any constant $ε>0$, a data structure of size $O(n)$, such that for any vertical query slab $Q$, the closest pair in the set $Q \cap S$ can be reported in $O(n^{1/2+ε})$ time. Prior to this work, no linear space data structure with sublinear query time was known.

Boris Aronov, Jean Cardinal, Justin Dallant et al.

In recent years, the Fiat-Naor function inversion scheme has been used to disprove conjectures in fine-grained complexity theory and design state of the art data structures for a number of combinatorial problems. We pursue this line of research by considering its application to data structures for searching in implicit sets, defined as the image of a function. We show that, if $f$ is of the form $[N]\to [2^{w}]^d$ for some $w=polylog(N)$ and is computable in constant time, then, for any $0<α<1$, we can obtain a data structure using $Õ(N^{1-α/3})$ space such that, for a given $d$-dimensional axis-aligned box $B$, we can search for some $x\in [N]$ such that $f(x) \in B$ in time $Õ(N^α)$. (Here the $Õ(.)$ notation omits polylogarithmic factors.) Using similar techniques, we further obtain - data structures for range counting and reporting, predecessor, selection, ranking queries, and combinations thereof, on the set $f([N])$, - data structures for preimage size and preimage selection queries for a given value of $f$, and - data structures for selection and ranking queries on geometric quantities computed from tuples of points in $d$-space. These results unify and generalize previously known results on 3SUM-indexing and string searching, and are widely applicable as a black box to a variety of problems. In particular, we give a data structure for a generalized version of gapped string indexing, and show how to preprocess a set of points on an integer grid in order to efficiently compute (in sublinear time), for points contained in a given axis-aligned box, their Theil-Sen estimator, the $k$th largest area triangle, or the induced hyperplane that is the $k$th furthest from the origin.

Ivor van der Hoog, John Iacono, Eva Rotenberg et al.

A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push($x_i$) pushes a new value $x_i$ onto the heap, and DecreaseKey($i$, $v$) decreases the value $x_i$ to $v$. A working-set heap is a heap that supports the $x_i \gets$ pop$()$ operation in $O(\log Γ(x_i) )$ time where $Γ(x_i)$ is the size of the \emph{working set}: the number of elements that were pushed onto the heap while $x_i$ was in the heap. The goal of working set heap design is to maintain the working set property while minimizing the overhead of the Push and DecreaseKey operations. On a word RAM, there exist working set heaps that support Push and DecreaseKey in amortized constant time. In this paper, we show via a simple construction that pointer machines, one of the most general and least-assuming computational models, support working set heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann time. A by-product of this analysis is that Dijkstra's shortest path algorithm can be near-universally optimal on a pointer machine -- incurring only an additive $O(m \, α(m))$ overhead compared to the optimal running time for distance ordering, where $m$ denotes the number of edges in the graph.