Sebastian Wild CV · page 1 of 10
Sebastian Wild
University of Liverpool
School of Electrical Engineering, Electronics & Computer Science
Department of Computer Science
Ashton Building, Ashton Street
Liverpool L69 3BX, United Kingdom
wild@liverpool.ac.uk
March 11, 2022
Employment
since 2019 Lecturer (Assistant Professor)
Department of Computer Science · University of Liverpool
2017–2019 Postdoctoral Fellow and Sessional Instructor
David R. Cheriton School of Computer Science · University of Waterloo
2012–2017 Wissenschaftlicher Mitarbeiter (research assistant)
Department of Computer Science · University of Kaiserslautern
parental leave for 6 months (Dec. 2013 – Jan. 2014, May – June 2015, Nov. – Dec. 2016)
Education
Dr. rer. nat.
(equiv. to Ph.D.)
Department of Computer Science · University of Kaiserslautern · 2016
Dissertation summa cum laude
Title:
Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential
Supervisor: Prof. Dr. Markus Nebel
2nd Reviewer: Prof. Robert Sedgewick (Princeton University)
3rd Reviewer: Univ.-Prof. Dr. Martin Dietzfelbinger (TU Ilmenau)
M. Sc. Department of Computer Science · University of Kaiserslautern · 2012
Final grade 1.1
B. Sc. Department of Computer Science · University of Kaiserslautern · 2010
Final grade 1.3
Abitur Kurfürst-Ruprecht-Gymnasium · Neustadt a. d. Weinstraße · 2006
Final grade 1.1
Sebastian Wild CV · page 2 of 10
Publications
Preprints and details at
www.wild-inter.net/publications.
(Titles are clickable links).
NB: The convention in algorithms for author lists
is alphabetical by last name.
Peer-Reviewed Conference Papers
[c16] Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev
Symposium on Theory of Computing (STOC) 2022
to appear
[c15] Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Leszek G ˛asieniec, Benjamin Smith, and Sebastian Wild
Symposium on Algorithm Engineering and Experiments (ALENEX) 2022
C. A. Phillips and B. Speckmann (eds.): ALENEX 2022, pp 91–103
[c14] Succinct Euler-Tour Trees
Travis Gagie and Sebastian Wild
Canadian Conference on Computational Geometry (CCCG) 2021
M. He and D. Sheehy (eds.): CCCG 2021, pp 368–376
[c13] 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
European Symposium on Algorithms (ESA) 2021
to appear
[c12] Lazy Search Trees
Bryce Sandlund and Sebastian Wild
Foundations of Computer Science (FOCS) 2020
S. Irani (ed.): FOCS 2020, IEEE, 2020, pp 704–715
[c11] 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
International Symposium on Algorithms and Computation (ISAAC) 2020
Y. Cao, SW. Cheng, M. Li (eds.): ISAAC 2020, LIPIcs 181, Dagstuhl, 2020, pp 25:1–25:18
[c10] Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao, and Sebastian Wild
Algorithms and Data Structures Symposium (WADS) 2019
Z. Friggstad, JR. Sack, M. Salavatipour (eds.): WADS 2019, LNCS 11646, Springer, 2019, pp 395–408
[c9] Sesquickselect: One and a half pivots for cache-efficient selection
Conrado Martínez, Markus E. Nebel, and Sebastian Wild
Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2019
M. Mishna and J.I. Munro (eds.): ANALCO 2019, SIAM, pp 54–66
Sebastian Wild CV · page 3 of 10
[c8] Median-of-k Jumplists and Dangling-Min BSTs
Markus E. Nebel, Elisabeth Neumann, and Sebastian Wild
Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2019
M. Mishna and J.I. Munro (eds.): ANALCO 2019, SIAM, pp 74–86
[c7] Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally
Adapt to Existing Runs
J. Ian Munro and Sebastian Wild
European Symposium on Algorithms (ESA) 2018
Y. Azar, H. Bast, G. Herman (eds.): ESA 2018, LIPIcs 112, Dagstuhl, 2018, pp 63:1–63:16
[c6] Average Cost of QuickXsort with Pivot Sampling
Sebastian Wild
International Conference on Probabilistic, Combinatorial and
Asymptotic Methods for the Analysis of Algorithms (AofA) 2018
MD. Ward, JA. Fill (eds.): AofA 2018, LIPIcs vol. 110, pp 36:1–36:19
[c5] Quicksort Is Optimal for Many Equal Keys
Sebastian Wild
Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2018
M. Nebel, S. Wagner (eds.): ANALCO 2018, SIAM, pp 8–22
[c4] Analysis of Branch Misses in Quicksort
Conrado Martínez, Markus E. Nebel, and Sebastian Wild
Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2015
R. Sedgewick, MD. Ward (eds.): ANALCO 2015, SIAM, pp 114–128
[c3] 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 (AofA) 2014
M. Bousquet-Mélou, M. Soria (eds.): DMTCS-HAL Proceedings Series, vol. BA, pp 325–338
[c2] Engineering Java 7’s Dual Pivot Quicksort Using MaLiJAn
Sebastian Wild, Markus E. Nebel, Raphael Reitzig, and Ulrich Laube
Meeting on Algorithm Engineering and Experiments (ALENEX) 2013
P. Sanders, N. Zeh (eds.): ALENEX 2013, SIAM, pp 55–69
[c1] Average Case Analysis of Java 7’s Dual Pivot Quicksort
Sebastian Wild and Markus E. Nebel
European Symposium on Algorithms (ESA) 2012
L. Epstein and P. Ferragina (eds.): ESA 2012, LNCS 7501, Springer, pp 825–836.
Peer-Reviewed Journal Articles
[j7] QuickXsort – A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin Weiß, and Sebastian Wild
Algorithmica 82, 3, pp 509–588, 2020
Sebastian Wild CV · page 4 of 10
[j6] Dual-pivot and beyond: The potential of multiway partitioning in quicksort
Sebastian Wild
Distinguished Dissertations in
it – Information Technology,
60, 3, pp 173–177,
2018
[j5] Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum
Length You Can Cut k Times from Given Sticks
Raphael Reitzig and Sebastian Wild
Algorithmica 80, 11, pp 3365–3396, 2018
[j4] Analysis of Pivot Sampling in Dual-Pivot Quicksort
Markus E. Nebel, Sebastian Wild, and Conrado Martínez
Algorithmica 75, 4, pp 632–683, 2016
[j3] Analysis of Quickselect under Yaroslavskiy’s Dual-Pivoting Algorithm
Sebastian Wild, Markus E. Nebel, and Hosam Mahmoud
Algorithmica 74, 1, pp 485–506, 2016
[j2] 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, 2015
[j1] JAguc – A Software Package for Environmental Diversity Analyses
Markus E. Nebel, Sebastian Wild, Michael Holzhauser, Lars Hüttenberger,
Raphael Reitzig, Matthias Sperber, and Thorsten Stoeck
Journal of Bioinformatics and Computational Biology 9, 6, pp 749–773, 2011
Textbooks
[b1] Entwurf und Analyse von Algorithmen
(Design and Analysis of Algorithms)
Markus Nebel and Sebastian Wild · Springer Vieweg · 2018
Theses
[t3]
Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential
Dissertation · University of Kaiserslautern · 2016
[t2] Java 7’s Dual Pivot Quicksort
Master’s Thesis · University of Kaiserslautern · 2012
[t1] An Earley-style Parser for Solving the RNA-RNA Interaction Problem
Bachelor’s Thesis · University of Kaiserslautern · 2010
Sebastian Wild CV · page 5 of 10
Manuscripts in Preparation & Working Papers
[m5] Succinct Permutation Graphs
Konstantinos Tsakalidis, Sebastian Wild, and Viktor Zamaraev
[m4] Dynamic Optimality Refuted – For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild, and Lingyi Zhang
[m3] Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
J. Ian Munro, and Sebastian Wild
[m2] A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
Raphael Reitzig and Sebastian Wild
[m1] Reputation-Based Cooperation in Local Interaction: Evolution of Indirect Reciprocity
with Minimal Memory
·
Jano Costard, Sándor P. Fekete, Hella-Franziska Hoffmann,
Alexander Koch, Dominik Leipold, Jonas Radbruch, Maximilian Schlund, Jann
Spiess, Paul Stursberg, and Sebastian Wild
Other Publications
[O2] Quicksort mit zwei Pivots und mehr · Sebastian Wild
GI LNI Dissertations Band 17 – Ausgezeichnete Informatikdissertationen 2016
[O1] Why is Dual-Pivot Quicksort Fast? · Sebastian Wild
extended abstract for Theorietage 2015 (GI Workshop on Algorithms)
Awards and Honors
2017 GI Dissertationspreis 2016 · [t3]
Prize for best dissertation in computer science 2016 in Germany, Austria,
and Switzerland, jointly awarded by GI, SI, and OCG
2017 Nominated for Distinguished Teaching Award 2017 of University of Kaiserslautern
for the design of the interactive course Training für Programmierwettbewerbe
2013 Preis des Freundeskreises der TU Kaiserslautern · [t2]
Best Master’s Thesis in the Department of Computer Science 2012
2012 Best Paper Award at the European Symposium on Algorithms 2012 · [c1]
2009–2012 Scholarship of the German National Academic Foundation
Grant s and Funding
2021–2022 Travel Grant for research visit to Kostas Tsichlas
funded by The Royal Society, International Exchanges Program · volume £ 2 900
2020–2023 PhD studentship for Benjamin Smith
funded by School of Electrical Engineering and Computer Science, University of
Liverpool · 1 of 2 studentships in the department · volume £ 59 076
Sebastian Wild CV · page 6 of 10
2021 Workshop Algorithmic and probabilistic aspects of space efficiency
funded by London Mathematical Society, Department of Computer Science, and the
NeST Initiative of University of Liverpool · volume £ 940
2020 Travel Grant for research visit to Markus Lohrey
funded by the NeST Initiative of University of Liverpool · volume £ 940
Talks
Slides available at www.wild-inter.net/publications.
Invited Talks
2021 “Hypersuccinct Trees”
International Conference on Probabilistic, Combinatorial and Asymptotic
Methods for the Analysis of Algorithms (AofA) 2021 · 14 Jun. 2021
2021 “Quicksorts of the 21st Century”
Workshop Verified software: tools and experiments · Special event celebrating
quicksort’s 60th birthday · Isaac Newton Institute · 7 Jun. 2021
2019
“Dual-Pivot Quicksort and Beyond: An Analysis-of-Algorithms Perspective on Multiway Quicksort”
Computability in Europe 2019 ·
Special Session Smoothed and Probabilistic Analysis of Algorithms
Durham University · 17 Jul. 2019
2018 “Succinct Data Structures For Range Minimum Problems”
NSF Center for Science of Information · Purdue University · 24 Oct. 2018
2017 “Dual-Pivot Quicksort and Beyond”
Annual SPP Meeting of the DFG Schwerpunktprogramm Algorithms for Big Data
19 Oct. 2017
2016 “Dual-Pivot Quicksort and Beyond”
Research Seminar · Hasso-Plattner-Institut Potsdam · 6 Sep. 2016
Conference & Workshop Presentations
2019 “Second-Order Shape-Constrained Function Fitting” · [c10]
WADS 2019 · 6 Aug. 2019
2019 “Compressed Range-Minimum Queries: Average-Case Analysis of Search Trees Meets
Space-Efficient Data Structures” · [m3]
AofA Meeting · 24 Jun. 2019
2019 “Entropy Trees & Range-Minimum Queries In Optimal Average-Case Space” · [m3]
Dagstuhl Seminar 19 051 (Data Structures for the Cloud and External Memory Data)
28 Jan. 2019
2019 “Sesquickselect: One and a half pivots for cache-efficient selection” · [c9]
ANALCO Conference · 06 Jan. 2019
2018 “Nearly-optimal Mergesorts” · [c7]
ESA Conference · 20 Aug. 2018
2018 “Average Cost of QuickXsort with Pivot Sampling” · [c6]
AofA Conference · 28 June 2018
Sebastian Wild CV · page 7 of 10
2018 “Quicksort Is Optimal for Many Equal Keys” · [c5]
ANALCO Conference · 8 Jan. 2018
2017 “Median-of-k Quicksort is optimal for many equal keys”
AofA Meeting · 19 June 2017
2016 “Quicksort with Equal Keys”
Dagstuhl Seminar 16 101 (Data Structures and Advanced Models of Computation on Big Data)
7 March 2016
2015 “Why is Dual-Pivot Quicksort Fast?” · [O1]
GI Theorietage (Workshop) · 29 Sept. 2015
2015 “Analysis of Branch Misses in Quicksort” · [c4]
ANALCO Conference · 4 Jan. 2015
2014 “Pivot Sampling in Dual-Pivot Quicksort” · [c3]
AofA Conference · 16 June 2014
2014 “Dual-Pivot Quicksort – Asymmetries in Sorting”
Dagstuhl Seminar 14 091 (Data Structures and Advanced Models of Computation on Big Data)
25 March 2014
2013 “Engineering Java 7’s Dual Pivot Quicksort Using MaLiJAn” · [c2]
ALENEX Conference · 7 Jan. 2013
2013 “Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm”
AofA Meeting · 28 May 2013
2013 “Java 7’s Dual Pivot Quicksort”
FORMAT Workshop · 9 April 2013
2012 “Average Case Analysis of Java 7’s Dual Pivot Quicksort” · [c1]
ESA Conference · 11 Sept. 2012
Departmental Talks
2019 “Dual-Pivot Quicksort and Beyond” · University of Liverpool · 10 Dec. 2019
2017 “Dual-Pivot Quicksort and Beyond” · University of Waterloo · 1 Nov. 2017
2015 “Dual-Pivot Quicksort” · University of Kaiserslautern · 24 Mar. 2015
Sebastian Wild CV · page 8 of 10
Teaching Experience
Details on courses and teaching evaluations at www.wild-inter.net/teaching.
(Titles are clickable links).
Instructor of Record
Sole responsibility for module (give lectures, design assignments, take/design exams).
2022 Applied Algorithmics (COMP 526) · postgraduate level
2021/22 Communicating Computer Science (COMP 335) · third-year undergraduate
2021 Applied Algorithmics (COMP 526) · postgraduate level
2020 Applied Algorithmics (COMP 526)
2018 Data Structures and Data Management (CS 240) · undergraduate level
2017 Advanced Algorithmics: Strategies for Hard Problems · advanced postgraduate level
2017 Competitive Programming · undergraduate level
2016/17 Algorithms and Data Structures · undergraduate level, non-CS majors
Teaching Assistance
Responsible for tutorials (recruit student tutors, design assignments and exams, give exercise classes).
2015/16
2014
Introduction to the Mathematical Analysis of Algorithms
(original title: Algorithm Engineering) · advanced postgraduate level
2013/14 Computational Biology I: Alignments and Sequencing
advanced undergraduate level
2015/16
2014
2012/13
Computational Biology II: Signals, Phylogenetics and Structure Prediction
postgraduate level
2014/15 Design and Analysis of Algorithms · intermediate undergraduate level
2013 Combinatorial Algorithms: String Search, Compression, Networks,
and Random Generation · advanced undergraduate level
2013/14
2012/13
Proof Techniques · tutorial at introductory undergraduate level
Student Tutor
(grade assignments, give exercise class).
Formal Foundations of Programming
·
Software Development I: Introduction to Programming
·
Software Development III: Concurrency and Parallel Programming
Sebastian Wild CV · page 9 of 10
Super vised Students
PhD Students
2020–2024 Benjamin Smith
2021–2025 Eva Onokpasa
Selected Master’s Theses
2021 William Cawley Gelling · Title: 4-way Peeksort & 4-way Powersort
2020 Benjamin Smith · Title: Exact Solutions for the Bamboo Garden Trimming Problem · [c15]
Selected Bachelor’s Theses
2016 Marvin Peterson · Title: Experimental View on Cache Behavior of Search Trees
2015 Elisabeth Neumann · Title: Randomized Jumplists With Several Jump Pointers · [c8]
Ser vice
To Profession
Program
committees
LATIN 2022 · AofA 2022 · ESA 2019 · ANALCO 2019 · ANALCO 2018
Reviews
(journals)
ACM Journal of Experimental Algorithmics · ACM Transactions on Algorithms ·
Algorithmica · Bulletin of Mathematical Biology ·
Combinatorics, Probability & Computing · Discrete Applied Mathematics ·
IEEE Transactions on Computers · Information Processing Letters ·
International Journal of Computer Mathematics · Journal of Experimental Algorithmics ·
Mathematical Programming · Mathematics in Computer Science ·
Software: Practice and Experience · The Computer Journal ·
Theoretical Computer Science ·
Stochastics (Intern. J. of Probability and Stochastic Processes)
Reviews
(conferences)
SODA 2022
·
SOSA 2022
·
ISAAC 2021
·
STACS 2021
·
SoCG 2020
·
SODA 2020
·
SOFSEM 2020 · SPAA 2019 · SEA 2018 · WADS 2017 · SEA 2017 ·
ANALCO 2017 · AofA 2016 · SWAT 2014 · ANALCO 2014 · ESA 2013
To Department
since 2020 Coordinator of Outreach Activities of the department
2012 – 2017 Representative of Scientific Employees in Examination Board
Sebastian Wild CV · page 10 of 10
Additional Training
2020 Postgraduate Certificate Academic Practice
Level 7 qualification in Learning and Teaching in Higher Education
The Academy, University of Liverpool
2017 Teaching Development Seminar Series for Postdocs
Centre for Teaching Excellence, University of Waterloo · 6 – 10 Nov. 2017
2016 Lehre 2.0 – Lehren mit dem Internet
Workshop on including social media in teaching · 13 June 2016
2015 Meetings und Projektbesprechungen effizient und zielgerichtet leiten
Workshop on how to effectively chair a group meeting · 9 – 10 April 2015
Nonacademic Work Experience
Java Developer marketmaker Software AG (since 2012 part of vwd Vereinigte Wirtschaftsdienste GmbH)
Jul 2010 – Apr 2012 in term breaks
Developed server components for a web-based financial market-data solution.
Languages
German native
English fluent
French elementary
Spanish elementary
