List of Publications

Articles in Conference Proceedings

2026

• Partition-based Simple Heaps

  Gerth Stølting Brodal, John Iacono, Casper Moldrup Rysgaard, and Sebastian Wild  ⋅  LATIN 2026  ⋅  Apr 2026

• Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space

  Ziad Ismaili Alaoui, Detlef Plump, and Sebastian Wild  ⋅  SOSA 2026  ⋅  Jan 2026

2025

• Lazy B-Trees

  Casper Moldrup Rysgaard and Sebastian Wild  ⋅  MFCS 2025  ⋅  Jul 2025

• Succinct Preferential-Attachment Graphs

  Ziad Ismaili Alaoui, Namrata, and Sebastian Wild  ⋅  WG 2025  ⋅  Jun 2025

• Adaptive sorting for large keys, strings, and database rows

  Marius Kuhrt, Bernhard Seeger, Sebastian Wild, and Goetz Graefe  ⋅  BTW 2025  ⋅  Mar 2025

• Simple approximation algorithms for Polyamorous Scheduling

  Yuriy Biktairov, Leszek Gąsieniec, Wanchote Po Jiamjitrak, Namrata, Benjamin Smith, and Sebastian Wild  ⋅  SOSA 2025  ⋅  Jan 2025

2024

• An Optimal Randomized Algorithm for Finding the Saddlepoint

  Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild  ⋅  ESA 2024  ⋅  Sep 2024

• Deterministic Cache-Oblivious Funnelselect

  Gerth Stølting Brodal and Sebastian Wild  ⋅  SWAT 2024  ⋅  Jun 2024

• Polyamorous Scheduling

  Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild  ⋅  FUN 2024  ⋅  Jun 2024

• Towards Optimal Grammars for RNA Structures

  Eva Onokpasa, Sebastian Wild, and Prudence Wong  ⋅  DCC 2024  ⋅  Mar 2024

• Finding the saddlepoint faster than sorting

  Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild  ⋅  SOSA 2024  ⋅  Jan 2024

2023

• Funnelselect: Cache-oblivious multiple selection

  Gerth Stølting Brodal and Sebastian Wild  ⋅  ESA 2023  ⋅  Sep 2023

• RNA secondary structures: from ab initio prediction to better compression, and back

  Eva Onokpasa, Sebastian Wild, and Prudence Wong  ⋅  DCC 2023  ⋅  Mar 2023

• Multiway Powersort

  William Cawley Gelling, Markus E. Nebel, Benjamin Smith, and Sebastian Wild  ⋅  ALENEX 2023  ⋅  Jan 2023

2022

• Randomized Communication and Implicit Graph Representations

  Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev  ⋅  STOC 2022  ⋅  Jun 2022

• Towards the 5/6-Density Conjecture of Pinwheel Scheduling

  Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild  ⋅  ALENEX 2022  ⋅  Jan 2022

2021

• Succinct Euler-Tour Trees

  Travis Gagie and Sebastian Wild  ⋅  CCCG 2021  ⋅  Jun 2021

• Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures and range minima

  J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner, and Sebastian Wild  ⋅  ESA 2021  ⋅  Apr 2021

2020

• Lazy Search Trees

  Bryce Sandlund and Sebastian Wild  ⋅  FOCS 2020  ⋅  Dec 2020

• Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

  Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu  ⋅  ISAAC 2020  ⋅  May 2020

2019

• Efficient Second-Order Shape-Constrained Function Fitting

  David Durfee, Yu Gao, Anup B. Rao, and Sebastian Wild  ⋅  WADS 2019  ⋅  Aug 2019

• Median-of-k Jumplists and Dangling-Min BSTs

  Markus E. Nebel, Elisabeth Neumann, and Sebastian Wild  ⋅  ANALCO 2019  ⋅  Jan 2019

• Sesquickselect: One and a half pivots for cache-efficient selection

  Conrado Martínez, Markus Nebel, and Sebastian Wild  ⋅  ANALCO 2019  ⋅  Jan 2019

2018

• Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs

  J. Ian Munro and Sebastian Wild  ⋅  ESA 2018  ⋅  May 2018

• Average Cost of QuickXsort with Pivot Sampling

  Sebastian Wild  ⋅  AofA 2018  ⋅  Mar 2018

• Quicksort Is Optimal for Many Equal Keys

  Sebastian Wild  ⋅  ANALCO 2018  ⋅  Jan 2018

2015

• Analysis of Branch Misses in Quicksort

  Conrado Martínez, Markus Nebel, Sebastian Wild  ⋅  ANALCO 2015  ⋅  Jan 2015

2014

• Pivot Sampling in Dual-Pivot Quicksort—Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme

  Markus Nebel and Sebastian Wild  ⋅  AofA 2014  ⋅  Jun 2014

2013

• Engineering Java 7’s Dual-Pivot Quicksort Using MaLiJAn

  Sebastian Wild, Markus Nebel, Raphael Reitzig, and Ulrich Laube  ⋅  ALENEX 2013  ⋅  Jan 2013

2012

• Average-Case Analysis of Java 7’s Dual-Pivot Quicksort

  Sebastian Wild and Markus Nebel  ⋅  ESA 2012  ⋅  Sep 2012

Journal Articles

2025

• Randomized Communication and Implicit Graph Representations

  Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev  ⋅  TheoretiCS  ⋅  Jul 2025

2023

• A Simple and Fast Linear-Time Algorithm for Divisor Methods of Apportionment

  Raphael Reitzig, Sebastian Wild  ⋅  Mathematical Programming  ⋅  Feb 2023

2022

• Succinct Permutation Graphs

  Konstantinos Tsakalidis, Sebastian Wild, and Viktor Zamaraev  ⋅  Algorithmica  ⋅  Sep 2022

2020

• QuickXsort – A Fast Sorting Scheme in Theory and Practice

  Stefan Edelkamp, Armin Weiß, and Sebastian Wild  ⋅  Algorithmica (2020)  ⋅  Feb 2020

2018

• Dual-pivot and beyond: The potential of multiway partitioning in quicksort

  Sebastian Wild  ⋅  it – Information Technology (invited article)  ⋅  Jun 2018

2017

• Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks

  Raphael Reitzig, Sebastian Wild  ⋅  Algorithmica (2018)  ⋅  Nov 2017

2016

• Analysis of Pivot Sampling in Dual-Pivot Quicksort—A Holistic Analysis of Yaroslavskiy’s Partitioning Scheme

  Markus Nebel, Sebastian Wild, and Conrado Martínez  ⋅  Algorithmica (2016)  ⋅  Aug 2016

2015

• Average Case and Distributional Analysis of Dual-Pivot Quicksort

  Sebastian Wild, Markus Nebel, and Ralph Neininger  ⋅  TALG 11(3), art. 22 (2015)  ⋅  Jan 2015

2014

• Analysis of Quickselect under Yaroslavskiy’s Dual-Pivoting Algorithm

  Sebastian Wild, Markus Nebel and Hosam Mahmoud  ⋅  Algorithmica  ⋅  Nov 2014

2011

• JAguc – A Software Package for Environmental Diversity Analyses

  Markus Nebel, Sebastian Wild, Michael Holzhauser, Lars Hüttenberger, Raphael Reitzig, Matthias Sperber, and Thorsten Stoeck  ⋅  J. of Bioinformatics and Comp. Biology  ⋅  Dec 2011

Books

• Entwurf und Analyse von Algorithmen

  Markus Nebel, Sebastian Wild  ⋅  Springer Vieweg  ⋅  Apr 2018

Theses

• Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential

  Sebastian Wild  ⋅  Ph.D. Thesis  ⋅  Oct 2016

• Java 7’s Dual Pivot Quicksort

  Sebastian Wild  ⋅  Master's Thesis  ⋅  Aug 2012

• An Earley-style Parser for Solving the RNA-RNA Interaction Problem

  Sebastian Wild  ⋅  Bachelor's Thesis  ⋅  Jun 2010

Others

• Virtual-Memory PowerSort

  Finn Moltmann, Tamio-Vesa Nakajima, and Sebastian Wild  ⋅  arXiv  ⋅  May 2026

• Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs

  Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata, and Sebastian Wild  ⋅  arXiv  ⋅  Mar 2026

• A House Divided: Cooperation, Polarization, and the Power of Reputation

  Sebastian Wild, Phillip Keldenich, Jann Spiess, Maximilian Schlund, Jano Costard, Jonas Radbruch, Paul Stursberg, and Sándor Fekete  ⋅  Research Square  ⋅  Jul 2023

• Dynamic Optimality Refuted – For Tournament Heaps

  J. Ian Munro, Richard Peng, Sebastian Wild, and Lingyi Zhang  ⋅  arXiv  ⋅  Aug 2019

• Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space

  J. Ian Munro, and Sebastian Wild  ⋅  arXiv  ⋅  Mar 2019

• A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment

  Raphael Reitzig, Sebastian Wild  ⋅  arXiv  ⋅  Mar 2017