Sebastian Wild

I left Kaiserslautern in August 2017; I am now a postdoc in Ian Munro's group at University of Waterloo.
This page will no longer be updated; check my personal website for up-to-date information and contact.

Research Interests

My interests span several (loosely related) topics, including (but not limited to):

• Analytic Combinatorics
  Counting fancy structures by generating function techniques.
  If you don't know generating functions, get infected: Why Generating Functions Rule
• Practical Algorithmics
  In-detail “in vivo” analyses of real-world algorithms, both analytically and experimentally.
  See the work on Java 7's Dual-Pivot Quicksort. This article gives a brief summary of my findings.
  
• (Semi-) Automatic Algorithm Analysis
  Empirically estimating asymptotic growth of expected costs of algorithms.
  Check out our tool MaLiJAn!
• Bioinformatics
• RNA structure prediction methods
• Biodiversity estimation, see JAguc
• Game Theory
  Evolutionary models, especially attempts to explain the evolution of cooperation, formation of reputation and societies.

Publications

• Median-of-k Jumplists
  Markus E. Nebel, Elisabeth Neumann, and Sebastian Wild
  arXiv
• Sorting Discrete i.i.d. Inputs: Quicksort is Optimal
  Sebastian Wild
  arXiv
• Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential
  Sebastian Wild
  Doktorarbeit (Ph.D. Thesis)
  pdf, KLUEDO, ISBN, slides (defense)
• Why is Dual-Pivot Quicksort Fast?
  Sebastian Wild
  extended abstract for Theorietage 2015 (GI Workshop on Algorithms)
  Tagungsband, arXiv, slides
• A Simple and Fast Linear-Time Algorithm for Proportional Apportionment
  Raphael Reitzig and Sebastian Wild
  arXiv
  
• Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
  Raphael Reitzig and Sebastian Wild
  arXiv
• Analysis of Branch Misses in Quicksort
  Conrado Martínez, Markus E. Nebel and Sebastian Wild
  Meeting on Analytic Algorithmics and Combinatorics (ANALCO15)
  SIAM, arXiv, slides, DOI: 10.1137/1.9781611973761.11
• Analysis of Pivot Sampling in Dual-Pivot Quicksort
  Markus E. Nebel, Sebastian Wild and Conrado Martínez
  Algorithmica 75, 4, pp 632-683 (August 2016)
  springerlink, arXiv, DOI:10.1007/s00453-015-0041-7
  full version of the conference paper:
  Pivot Sampling in Dual-Pivot Quicksort
  Markus E. Nebel and Sebastian Wild
  International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms 2014 (AofA14)
  arXiv, slides, proceedings
• Evolution of Indirect Reciprocity in Lattice Populations:
  Reputation-Based Cooperation in Prisoner's Dilemma and Snowdrift Games
  Jano Costard, Sándor P. Fekete, Hella-Franziska Hoffmann, Alexander Koch, Dominik Leipold, Jonas Radbruch, Maximilian Schlund, Jann Spiess, Paul Stursberg and Sebastian Wild
  submitted
  
• Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
  Sebastian Wild, Markus E. Nebel and Hosam Mahmoud
  Algorithmica 74, 1, pp 485-506 (January 2016)
  springerlink, arXiv, DOI: 10.1007/s00453-014-9953-x
  also partially covered in Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
  Talk at the International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms 2013 (AofA13):
  slideshare, slides
• Average Case and Distributional Analysis of Dual Pivot Quicksort
  Sebastian Wild, Markus E. Nebel and Ralph Neininger
  ACM Transactions on Algorithms 11, 3, Article 22 (January 2015)
  Author-ized pdf, arXiv, DOI: 10.1145/2629340
  full version of the conference paper:
  Average Case Analysis of Java 7’s Dual Pivot Quicksort
  Sebastian Wild and Markus E. Nebel,
  European Symposium on Algorithms 2012 (ESA12)
  in L. Epstein and P. Ferragina (Eds.): ESA 2012, LNCS 7501, Springer, 2012, 825-836.
  Best Paper Award ESA 2012
  Referenced in Sedgewick's algorithms textbook! (see Chapter 2)
  arXiv, slides, DOI: 10.1007/978-3-642-33090-2_71
  Check out the animated visualization of the algorithm (thanks to Brad Lyon)!
• Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn
  Sebastian Wild, Markus E. Nebel, Raphael Reitzig and Ulrich Laube
  SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)
  pdf, slides, DOI: 10.1137/1.9781611972931.5
  
• JAguc - a software package for environmental diversity analyses
  M. E. Nebel, S. Wild, M. Holzhauser, L. Hüttenberger, R. Reitzig, M. Sperber, T. Stoeck,
  Journal of Bioinformatics and Computational Biology (2011) 9 (6): 749-773
  pdf, DOI: 10.1142/S0219720011005781
• Java 7's Dual Pivot Quicksort
  Master Thesis
  Available as printed paperback (AV Akademikerverlag, 2014)
  preprint pdf, ISBN: 978-3-639-67967-0!
  pdf, KLUEDO
• An Earley-style Parser for Solving the RNA-RNA Interaction Problem
  Bachelor Thesis
  pdf, KLUEDO

Supervised Theses

• Randomized Jumplists with Several Jump Pointers
  Elisabeth Neumann, Bachelor Thesis
  KLUEDO

Teaching

SS 17: Advanced Algorithmics, Competitive Programming

Past Teaching assistance

WS 16/17: Algorithmen und Datenstrukturen (OLAT)
WS 15/16: Algorithm Engineering and Computational Biology II
WS 14/15: Entwurf und Analyse von Algorithmen
SS 14: Algorithm Engineering and Computational Biology II
WS 13/14: Computational Biology I and Beweistechniken
SS 13: Kombinatorische Algorithmen
WS 12/13: Computational Biology II and Beweistechniken

As a student, I was tutor for the lectures Softwareentwicklung I, Softwareentwicklung III and Formale Grundlagen der Programmierung.

Fun Stuff

• Me repairing Don Knuth's slides at AofA14.
• Cameo appearance of two [not remotely similar looking] guys at two 2012 European events with different success
  in Sándor Fekete's lecture “Alorithmen und Datenstrukturen” (algorithms course of TU Braunschweig.)