I'm a postdoc at Max Planck Institute for Informatics, Department 1: Algorithms and Complexity. Previously, I worked as a Phd student under the supervision of László Kozma, at the theoretical computer science group at Freie Universität Berlin, Germany. My interest include data structures, graph algorithms, and combinatorics of permutations.
Room 312
Saarland Informatics Campus, Building E1 4
66123 Saarbrücken, Germany
benjamin.berendsohn@fu-berlin.de
Search trees on graphs.
PhD Thesis (2024)
[pdf]
Fast and simple unrooted dynamic forests.
2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 2024)
[arxiv 2023]
[ALENEX 2024]
Optimization with pattern-avoiding input.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)
[arxiv 2023]
[STOC 2024]
Fast approximation of search trees on trees with centroid trees.
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
[ICALP 2023]
Full version: [arxiv 2022]
Fixed-point cycles and EFX allocations.
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
[arxiv 2022]
[MFCS 2022]
The diameter of caterpillar associahedra.
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
[arxiv 2021]
[SWAT 2022]
An exact characterization of saturation for permutation matrices.
Combinatorial Theory 3(1) (2023)
[arxiv 2021]
[CT 2023]
Superseded draft: [arxiv 2020]
Splay trees on trees.
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
[arxiv 2020]
[SODA 2022]
Group Testing with Geometric Ranges.
2022 IEEE International Symposium on Information Theory (ISIT 2022)
[ISIT 2022]
Full version: [arxiv 2020]
Finding and Counting Permutations via CSPs.
Algorithmica 83 (2021)
[arxiv 2019]
[IPEC 2019]
[Algorithmica 2021]
Complexity of permutation pattern matching.
Master's thesis (2019)
[pdf]
Erratum: Problems/algorithms called on-line in the thesis are actually streaming problems/algorithms.