Benjamin Aram Berendsohn

Studies the problem of maintaining a vertex-weighted forest under edge deletions and the tree-min query, which returns the minimum vertex in a given component (i.e., tree). The worst-case complexity of this problem is \(\Theta(\log n)\) amortized time per operation, by a reduction from sorting. However, certain input forests are easier. For example, paths can be handled in \(O(1)\) amortized time per operation. We give a data structure that (informally) is optimal for any given input forest, i.e., a universally optimal data structure (c.f. the recent universally optimal variant of Dijkstra's algorithm). The paper contains a discussion of what universal optimality can mean for data structures (as opposed to classical, offline algorithms).

Considers the basic dynamic graph problems of maintaining component sums and rooted-subtree sums in vertex-weighted forests, under edge deletion and weight updates (cf. Universally Optimal Decremental Tree Minima, which studies a similar problem). Several tight results for rooted-subtree sums in the range between \(\Theta(\log n / \log\log n)\) and \(\Theta(\log n)\) time per operation. For component sums, we leave a gap between \(\Omega(1)\) and \(O(\log^*(n))\), but also give a provably optimal data structure.

Studies the space complexity of the Permutation Pattern Matching problem in a streaming setting. Solves all cases but the patterns 213 and 312 (and their complements), where we have an upper bound of roughly \(O(\sqrt{n})\), but no non-trivial lower bound. Based on parts of my Master's thesis.

Solves a generalization of sorting with partial information, where a set of elements needs to be sorted with comparisons, but some of the comparisons are given in advance. This paper studies a generalization where instead of a set of comparisons, an antimatroid that charaterizes possible orderings is given. It turns out the first optimal algorithm for sorting with partial information can be adapted to antrimatroids. This paper also contains a discussion of how to implement certain specific antimatroids as a data structure.

How much faster can two travelling salespeople visit a set of cities, compared to only one? We show that they always need at most \(\frac 1 2 + \frac 1 \pi \approx 0.818\) as much time, and this is tight. For higher dimensions, we show non-trivial but non-tight bounds.

Contains all my previous work on search trees on graphs, and more. These generalize classical binary search trees. Informally, the search space is generalized from a total order to a graph (mostly specifically a tree). Many questions for binary search trees can be generalized to search trees on graphs. My thesis discusses the model and its connections to tree-depth and tree-width; computing optimal static search trees for a given distribution; dynamic search trees and their application to dynamic forest data structures; and finally rotation distance between search trees, with connections to the theory of graph associahedra.

Considers three combinatorial and geometric problems under the restriction that the input must avoid a fixed permutation pattern. The problems are arborally satisfied superset, \(k\)-server, and Euclidean TSP. All these take a point set as input, which can be interpreted as a permutation for the sake of pattern avoidance. Our main result, a consequence of our bound for arborally satisfied superset, is that a dynamically optimal binary search tree algorithm takes \(O(n)\) time to execute a pattern-avoiding access sequence.

Uses our splay tree generalization (Splay trees on trees) to implement a dynamic forest data structure. There are some interesting commonalities with link-cut trees.

Shows that centroid trees are almost-optimal static search trees on trees, and presents fast algorithms to compute them.

Consider the complete bidirected graph, where each arc is labeled with a function \(f \colon [n] \rightarrow [n]\). A fixed-point cycle is a cycle in the graph where the composition of functions has a fixed point \(f(x)=x\). How many vertices are needed to guarantee a fixed-point cycle? We improve an existing cubic upper bound to almost-quadratic. The main application is an improved algorithm for approximate EFX allocations, an important problem in algorithmic game theory.

Studies the rotation distance between search trees on graphs, when the graph is a caterpillar tree. Presents tight bounds on the maximum distance between two search trees, for every caterpillar tree. The most interesting part is that both upper and lower bound use advanced tools from the theory of dynamic and static binary search trees.

Classical extremal problems involve forbiddding some pattern (e.g., a subgraph) and then finding the maximum weight (e.g., number of edges) in objects of a certain size (e.g., number of vertices). Besides undirected graphs, such problems can be defined for ordered, directed, etc. graphs. Here, we study 0-1-matrices, or, equivalently, ordered bipartite graphs. Instead of the extremal problem, we study the saturation problem, where we want to find the minimum-weight object that only just avoids the pattern. As the title says, the paper solves the saturation problem for all patterns that are permutation matrices.

Studies static and dynamic search trees on trees. We give a PTAS for computing optimal static search trees (given a search distribution), and a generalization of splay trees to a tree-search model. My PhD Thesis contains an expanded discussion, including an FPTAS for static trees using a different approach. Fast and simple unrooted dynamic forests uses our Splay tree generalization to implement a dynamic forest data structure.

A combinatorial look at nonadaptive group testing where test items are points, and tests are axis-parallel boxes. We prove lower and upper bounds on the number of tests required to find one or more defective items. One of the upper bounds uses a neat connection to the Zarankiewicz problem from extremal combinatorics.

Contains an expanded version of Finding and Counting Permutations via CSPs and a slightly different version of Permutation patterns in streams.
Erratum: Problems/algorithms called on-line in the thesis should be called streaming problems/algorithms.

Improved exponential algorithms for the Permutation Pattern Matching and Permutation Pattern Counting problems, and an ETH-hardness result for counting. An expanded presentation and more hardness results are found in my Master's thesis.