2 citations · 5 across the 10 of their papers we have counts for
17 papers
The Sync Heap: Delete First, Ask Questions Later
Benjamin Aram Berendsohn, Egor Gorbachev, László Kozma
Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the comparison model at…
Fast decremental tree sums in forests
Benjamin Aram Berendsohn, Marek Sokołowski
We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size under edge deletions, weight updates, and a…
Universally Optimal Decremental Tree Minima
Benjamin Aram Berendsohn
An algorithm on weighted graphs is called universally optimal if it is optimal for every input graph, in the worst case taken over all weight assignments. Informally, this means th…
When is String Reconstruction using de Bruijn Graphs Hard?
Ben Bals, Sebastiaan van Krieken, Solon P. Pissis +2
The reduction of the fragment assembly problem to (variations of) the classical Eulerian trail problem [Pevzner et al., PNAS 2001] has led to remarkable progress in genome assembly…
Optimal antimatroid sorting
Benjamin Aram Berendsohn
The classical comparison-based sorting problem asks us to find the underlying total order of a given set of elements, where we can only access the elements via comparisons. In this…
Permutation patterns in streams
Benjamin Aram Berendsohn
Permutation patterns and pattern avoidance are central, well-studied concepts in combinatorics and computer science. Given two permutations and , the pattern matching proble…
Balanced TSP partitioning
Benjamin Aram Berendsohn, Hwi Kim, László Kozma
The traveling salesman problem (TSP) famously asks for a shortest tour that a salesperson can take to visit a given set of cities in any order. In this paper, we ask how much faste…
Fast and simple unrooted dynamic forests
Benjamin Aram Berendsohn
A dynamic forest data structure maintains a forest (and associated data like edge weights) under edge insertions and deletions. Dynamic forests are widely used to solve online and…
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complex…
Fast approximation of search trees on trees with centroid trees
Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan +1
Search trees on trees (STTs) generalize the fundamental binary search tree (BST) data structure: in STTs the underlying search space is an arbitrary tree, whereas in BSTs it is a p…
Fixed-point cycles and EFX allocations
Benjamin Aram Berendsohn, Simona Boyadzhiyska, László Kozma
We study edge-labelings of the complete bidirected graph with functions from the set to itself. We call a cycle in $\o…
The diameter of caterpillar associahedra
Benjamin Aram Berendsohn
The caterpillar associahedron is a polytope arising from the rotation graph of search trees on a caterpillar tree , generalizing the rotation graph of binary se…
An exact characterization of saturation for permutation matrices
Benjamin Aram Berendsohn
A 0-1 matrix contains a 0-1 matrix pattern if we can obtain from by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function $\…
Matrix patterns with bounded saturation function
Benjamin Aram Berendsohn
A 0-1 matrix contains a 0-1 matrix pattern if we can obtain from by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function $\…
Splay trees on trees
Benjamin Aram Berendsohn, László Kozma
Search trees on trees (STTs) are a far-reaching generalization of binary search trees (BSTs), allowing the efficient exploration of tree-structured domains. (BSTs are the special c…
Geometric group testing
Benjamin Aram Berendsohn, László Kozma
Group testing is concerned with identifying defective items in a set of items, where each test reports whether a specific subset of items contains at least one defective. I…
Finding and counting permutations via CSPs
Benjamin Aram Berendsohn, László Kozma, Dániel Marx
Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1…