List of Publications

Publications by date

2024

• An Optimal Randomized Algorithm for Finding the Saddlepoint

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

• Deterministic Cache-Oblivious Funnelselect

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

• Polyamorous Scheduling

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

• Towards Optimal Grammars for RNA Structures

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

• Finding the saddlepoint faster than sorting

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

2023

• Funnelselect: Cache-oblivious multiple selection

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

• 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, Jul 2023
  Research Square

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

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

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

  Raphael Reitzig, Sebastian Wild, Feb 2023
  Mathematical Programming

• Multiway Powersort

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

2022

• Succinct Permutation Graphs

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

• Randomized Communication and Implicit Graph Representations

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

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

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

2021

• Succinct Euler-Tour Trees

  Travis Gagie and Sebastian Wild, Jun 2021
  CCCG 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, Apr 2021
  ESA 2021

2020

• Lazy Search Trees

  Bryce Sandlund and Sebastian Wild, Dec 2020
  FOCS 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, May 2020
  ISAAC 2020

• QuickXsort – A Fast Sorting Scheme in Theory and Practice

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

2019

• Dynamic Optimality Refuted – For Tournament Heaps

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

• Efficient Second-Order Shape-Constrained Function Fitting

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

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

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

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

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

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

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

2018

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

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

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

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

• Entwurf und Analyse von Algorithmen

  Markus Nebel, Sebastian Wild, Apr 2018
  Springer Vieweg

• Average Cost of QuickXsort with Pivot Sampling

  Sebastian Wild, Mar 2018
  AofA 2018

• Quicksort Is Optimal for Many Equal Keys

  Sebastian Wild, Jan 2018
  ANALCO 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, Nov 2017
  Algorithmica (2018)

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

  Raphael Reitzig, Sebastian Wild, Mar 2017
  arXiv

2016

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

  Sebastian Wild, Oct 2016
  Ph.D. Thesis

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

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

2015

• Average Case and Distributional Analysis of Dual-Pivot Quicksort

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

• Analysis of Branch Misses in Quicksort

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

2014

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

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

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

  Markus Nebel and Sebastian Wild, Jun 2014
  AofA 2014

2013

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

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

2012

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

  Sebastian Wild and Markus Nebel, Sep 2012
  ESA 2012

• Java 7’s Dual Pivot Quicksort

  Sebastian Wild, Aug 2012
  Master's Thesis

2011

• JAguc – A Software Package for Environmental Diversity Analyses

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

2010

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

  Sebastian Wild, Jun 2010
  Bachelor's Thesis