2 citations · 5 across the 10 of their papers we have counts for
12 papers · 1 filter
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…
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…
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…
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…