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.

Research

• 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, preprint 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 ...

(Old) projects

• WikipediaVision is an (almost) real-time visualization of anonymous Wikipedia edits. Mentioned on NPR, The New Yorker (link), O'Reilly Radar, Chip.de and elsewhere. Exhibited for 5 months (in 2009) at the Museum of Communication in Bern, Switzerland and installed at parties.


• Recursi is a recursive memory/logic puzzle.


• Visualization of the Cuckoo hashing data structure.


• more projects ...

Misc.

Books I've read recently around 2015

• Random blog posts
• Have the same name?
• Some favorites

mmvii-mmxxiii László Kozma < kozma@cs.uni-saarland.de >
Last updated .   RSS