7 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…
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…
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 prob…