Sebastian Wild CV · page 1 of 12
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
November 28, 2023
Employment
since 2023 Senior Lecturer (Associate Professor)
2019–2023 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
Education
Dr. rer. nat.
(equiv. to Ph.D.)
Department of Computer Science · University of Kaiserslautern · 2016
Dissertation
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
B. Sc. Department of Computer Science · University of Kaiserslautern · 2010
Abitur
(equiv. to A-levels)
Kurfürst-Ruprecht-Gymnasium · Neustadt a. d. Weinstraße · 2006
Sebastian Wild CV · page 2 of 12
Publications
Preprints and details at
www.wild-inter.net/publications.
(Titles are clickable links).
NB: The convention in algorithms for author lists
is in alphabetic order by last name.
Peer-Reviewed Conference Proceedings
[c20] Finding the saddlepoint faster than sorting
Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild
Symposium on Simplicity in Algorithms (SOSA) 2024
to be presented
[c19] Funnelselect: Cache-oblivious multiple selection
Gerth Stølting Brodal and Sebastian Wild
European Symposium on Algorithms (ESA) 2023
I. L. Gørtz, M. Farach-Colton, S. Puglisi, G. Herman (eds): ESA 2023, LIPIcs 274, pp 25:1–25:17
[c18] RNA secondary structures: from ab initio prediction to better compression, and back
Evarista Onokpasa, Sebastian Wild, and Prudence W. H. Wong
Data Compression Conference (DCC) 2023
DCC 2023, IEEE, pp 278–287
[c17] Multiway Powersort
William Cawley Gelling, Markus Nebel, Benjamin Smith, and Sebastian Wild
Symposium on Algorithm Engineering and Experiments (ALENEX) 2023
ALENEX 2023, ACM, pp 190–200
[c16] Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev
Symposium on Theory of Computing (STOC) 2022
STOC 2022, ACM, pp 1220–1233
[c15] Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Leszek Gąsieniec, 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
P. Mutzel, R. Pagh, G. Herman (eds.): ESA 2021, LIPIcs 204, pp 70:1–70:18
Sebastian Wild CV · page 3 of 12
[c12] Lazy Search Trees
Bryce Sandlund and Sebastian Wild
Foundations of Computer Science (FOCS) 2020
S. Irani (ed.): FOCS 2020, IEEE, 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, 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, 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
[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, 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 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
Sebastian Wild CV · page 4 of 12
[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
[j9] A Simple and Fast Linear-Time Algorithm for Divisor Methods of Apportionment
Raphael Reitzig and Sebastian Wild
Mathematical Programming B, 2023
[j8] Succinct Permutation Graphs
Konstantinos Tsakalidis, Sebastian Wild, and Viktor Zamaraev
Algorithmica 85, 2, pp 509–543, 2022
[j7] QuickXsort – A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin Weiß, and Sebastian Wild
Algorithmica 82, 3, pp 509–588, 2020
[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
Sebastian Wild CV · page 5 of 12
[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
Working Papers & Technical Reports
[m4] 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, In Review
[m3] Dynamic Optimality Refuted – For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild, and Lingyi Zhang
[m2] Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
J. Ian Munro, and Sebastian Wild
[m1] A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
Raphael Reitzig 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
2023 Guild Awards 2023 – Teacher of the Year (Science & Engineering)
Prize awarded by the Guild of Students of University of Liverpool by nomination
awarded to one academic in each of the three Faculties
Sebastian Wild CV · page 6 of 12
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
Grants and Funding
Principal Investigator
2023–2026
New Investigator Award
·
Engineering and Physical Sciences Research Council (EPSRC)
Computing over Compressed Graph-Structured Data
volume £ 519 180 (full economic cost)
2022–2023 Impact Accelerator Fund for developing impact case
Improved Sorting Algorithms for programming libraries
funded by School of Electrical Engineering, Electronics, and Computer Science,
University of Liverpool · volume £ 16 000
2022 Visiting Fellowship for hosting Gerth Stølting Brodal
funded by Department of Computer Science, University of Liverpool
1 of 4 funded Visiting Fellows · volume £ 700
2021–2022 International Exchanges Program · The Royal Society
Lazy Finger Search Trees
travel grant for research visit to Kostas Tsichlas (Patras, Greece) · volume £ 2 900
2020–2023 PhD studentship for Benjamin Smith
funded by School of Electrical Engineering, Electronics, and Computer Science,
University of Liverpool · 1 of 2 studentships in the department · volume £ 59 076
2021 Workshop Algorithmic and probabilistic aspects of space efficiency
funded by London Mathematical Society, Department of Computer Science, and the
EEECS School NeST Initiative of University of Liverpool · volume £ 940
2020 Travel Grant for research visit to Markus Lohrey
EEECS School NeST Initiative of University of Liverpool · volume £ 940
Co-Investigator
2021–2022 International Exchanges Program · The Royal Society
Decomposition techniques for graphs classes of bounded width parameters and their applications
PI Viktor Zamaraev; part of project team · volume £ 12 000
Sebastian Wild CV · page 7 of 12
Talks
Slides available at www.wild-inter.net/publications.
Invited Talks
2023 “Quicksort, Timsort, Powersort” · [c7], [c17]
Warwick CS Colloquium · University of Warwick · 15 Nov. 2023
2023 “Quicksort, Timsort, Powersort”
CS Lectures · IT University of Copenhagen · 9 Nov. 2023
2023 “Quicksort, Timsort, Powersort: Algorithmic ideas, engineering tricks, and trivia behind
CPython’s new sorting algorithm” · [c7], [c17]
PyCon US 2023 · 22 Apr. 2023
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
2023 “Funnelselect: Cache-Oblivious Multiple Selection‘ · [c19]
ESA 2023 · 6 Sept. 2023
2023 “Quicksort, Timsort, Powersort”
Dagstuhl Seminar 23 211 (Scalable Data Structures) · 22 May 2023
2022 “On the combinatorics of space-efficient data structures”
Banff International Research Station Workshop 22w5004
(Analytic and Probabilistic Combinatorics) · 15 Nov. 2022
2022 “Demystifying Neural Networks (and outreach during lockdown)” · tiny.cc/ai-course
Creative Mathematical Science Communication 2022 · 20 Apr. 2022
2021 “Lazy Search Trees” · [c12]
Dagstuhl Seminar 21 071 (Scalable Data Structures) · 16 Feb. 2021
2019 “Second-Order Shape-Constrained Function Fitting” · [c10]
WADS 2019 · 6 Aug. 2019
Sebastian Wild CV · page 8 of 12
2019 “Compressed Range-Minimum Queries: Average-Case Analysis of Search Trees Meets
Space-Efficient Data Structures” · [m2]
AofA Meeting · 24 Jun. 2019
2019 “Entropy Trees & Range-Minimum Queries In Optimal Average-Case Space” · [m2]
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
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 & Seminar Talks
2023 “Quicksort, Timsort, Powersort”
SSLC Distinguished Lecture Series · University of Liverpool · 17 Apr. 2023
Sebastian Wild CV · page 9 of 12
2022 “Putting your graphs on a diet”
Durham-Liverpool Synergy Networks Seminar · 27 Oct. 2022
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
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).
2024 Advances in Theoretical Computer Science (COMP 555) · postgraduate level
2023 Efficient Algorithmics (COMP 526) · postgraduate level
2023 Advances in Theoretical Computer Science (COMP 555) · postgraduate level
2022 Efficient Algorithmics (COMP 526) · postgraduate level
2022/23 Communicating Computer Science (COMP 335) · third-year undergraduate
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) · postgraduate level
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
Sebastian Wild CV · page 10 of 12
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
Super vised Students
PhD Students
2020–2024 Benjamin Smith
2021–2025 Eva Onokpasa
Selected Ma ster’s Theses
2021 William Cawley Gelling · Title: 4-way Peeksort & 4-way Powersort · [c17]
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
AofA 2024 (Co-Chair)
SOFSEM 2023 · 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)
Sebastian Wild CV · page 11 of 12
Reviews
(conferences)
STOC 2023
·
ESA 2023
·
MFCS 2023
·
IWOCA 2023
·
WABI 2022
·
ICALP 2022
·
SODA 2022 · SOSA 2022 · ISAAC 2021 · STACS 2021 · ESA 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 2022 Lead of the Recruitment, Outreach, and Public Relations group
of the School of Electrical Engineering, Electronics, and Computer Science
University of Liverpool
since 2020 Coordinator of Outreach Activities of the Department of Computer Science
University of Liverpool
2012 – 2017 Representative of Scientific Employees in Board of Examiners
(Prüfungsausschuss) · TU Kaiserslautern
Additional Training
2023 Knowledge Transfer Training Programme
Skillfluence & The Academy, University of Liverpool
2020 Fellow of the Higher Education Academy
Recognition of teaching experience through the ULTRA program
Advance HE & 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.
Sebastian Wild CV · page 12 of 12
Languages
German native
English fluent
French elementary
Spanish elementary
