László Kozma
change
Email address: kozma@cs.uni-saarland.de
About | Research | Projects | Misc. | Blog
About
I am a researcher in computer science, interested in data structures, algorithms, combinatorics, and other related (and unrelated) topics. Since 2018 I work as an assistant professor at Freie Universität Berlin, in the Theoretical Computer Science group (semi-official page).
I obtained my PhD at Saarland University in Saarbrücken, Germany, where my advisor was Raimund Seidel. Afterwards I spent a year as a postdoc at Tel Aviv University, hosted by Haim Kaplan and Yossi Azar, and a year at TU Eindhoven, hosted by Nikhil Bansal. A long time ago I worked and/or studied at Helsinki University of Technology (later renamed Aalto University), and TU Cluj in Romania, where I'm actually from.
Below you can find links to my research work and some fun projects I work(ed) on.
(recent and representative work — here is a more complete list with summaries, slides, and other links)
- NEW: Theoretical Analysis of Byte-Pair Encoding
with Johannes Voderholzer, preprint 2024. [pdf]
- NEW: Online sorting and online TSP: randomized, stochastic, and high-dimensional
with Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, ESA 2024. [pdf]
- NEW: Non-adaptive Bellman-Ford: Yen's improvement is optimal
with Jialu Hu, preprint 2024. [pdf]
- NEW: An optimal randomized algorithm for finding the saddlepoint
with Justin Dallant, Frederik Haagensen, Riko Jacob, Sebastian Wild, ESA 2024. [pdf]
- NEW: Finding the saddlepoint faster than sorting
with Justin Dallant, Frederik Haagensen, Riko Jacob, Sebastian Wild, SOSA@SODA 2024. [pdf]
- NEW: Optimization with pattern-avoiding input
with Benjamin Aram Berendsohn, Michal Opler, STOC 2024. [pdf]
- NEW: Fast approximation of search trees on trees with centroid trees
with Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan, ICALP 2023. [pdf]
- Fixed-point cycles and EFX allocations
with Benjamin Aram Berendsohn, Simona Boyadzhiyska, MFCS 2022. [pdf]
- Splay trees on trees
with Benjamin Aram Berendsohn, SODA 2022. [pdf]
- Analysis of smooth heaps and slim heaps
with Maria Hartmann, Corwin Sinnamon, Robert E. Tarjan, ICALP 2021. [pdf] [smooth-heap.c] [slim-heap.c]
- Finding and counting permutations via CSPs
with Benjamin Aram Berendsohn, Dániel Marx, IPEC 2019.
(Journal version: Algorithmica, Vol 83(8), 2021, by invitation.)
[pdf]
- Time- and space-optimal algorithm for the many-visits TSP
with André Berger, Matthias Mnich, Roland Vincze, SODA 2019.
(Journal version: ACM TALG, Vol 16(3), 2020.)
[pdf]
- Selection from heaps, row-sorted matrices and X + Y using soft heaps
with Haim Kaplan, Or Zamir, Uri Zwick, SOSA@SODA 2019. [pdf]
- Improved bounds for multipass pairing heaps and path-balanced binary search trees
with Dani Dorfman, Haim Kaplan, Seth Pettie, Uri Zwick, ESA 2018. [pdf]
- Smooth heaps and a dual view of self-adjusting data structures
with Thatchaphol Saranurak, STOC 2018.
(Journal version: SICOMP, Vol 49(5), 2020, by invitation.)
[pdf] [smooth-heap.c] [slim-heap.c]
- Maximum Scatter TSP in Doubling Metrics
with Tobias Mömke, SODA 2017. [pdf]
- Binary search trees, rectangles and patterns, PhD thesis, Saarland University, 2016.
[pdf]
- Pattern-avoiding access in binary search trees
with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Thatchaphol Saranurak, FOCS 2015. [pdf]
- Shattering, Graph Orientations, and Connectivity
with Shay Moran, Electronic Journal of Combinatorics, Vol 20(3), 2013. [pdf]
- Inequalities cheat sheet is a collection of important inequalities in mathematics.
- more publications ...
Misc.
Books I've read recently around 2015
mmvii-mmxxiv László Kozma < kozma@cs.uni-saarland.de >
Last updated
. RSS
|