Sebastian Wild CV · page 1 of 8
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@liv.ac.uk
5 Elms Park
Wirral CH61 9PJ
United Kingdom
+44 7907 529 281
sebawild@gmail.com
www.wild-inter.net
January 31, 2020
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
paternal 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 Title: Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning
and Its Practical Potential
M. Sc. Department of Computer Science, University of Kaiserslautern, 2012
B. Sc. Department of Computer Science, University of Kaiserslautern, 2010
Publications
Preprints and details at www.wild-inter.net/publications.
(Titles are clickable links).
Peer-Reviewed Conference Papers
[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
[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
[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
Seba stian Wild CV · page 2 of 8
[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
in Y. Azar, H. Bast, G. Herman (Eds.): ESA 2018, LIPIcs 112, Dagstuhl, 2018, 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 Algor ithms (AofA) 2018
Ward M. D., Fill J. A. (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
Nebel M., Wagner S. (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
Sedgewick R., Ward M. D. (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 Algor ithms (AofA) 2014
Bousquet-Mélou M., Soria M. (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
Sanders P., Zeh N. (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
Epstein L. and Ferragina P. (eds.): ESA 2012, LNCS 7501, Springer, pp 825–836.
Peer-Reviewed Journal Articles
[j6] QuickXsort – A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin Weiß, and Sebastian Wild
Algorithmica online first 2019
[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)
Seba stian Wild CV · page 3 of 8
[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
Manuscripts in Preparation & Working Papers
[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
Seba stian Wild CV · page 4 of 8
Other Publications
[O3] Dual-pivot and beyond: The potential of multiway partitioning in quicksort
Sebastian Wild
Distinguished Dissertations in it – Information Technology, vol 60, 3, pp 173–177
[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
Talks
Slides available at www.wild-inter.net/publications.
Invited Talks
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
Seba stian Wild CV · page 5 of 8
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
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
Seba stian Wild CV · page 6 of 8
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 course (give lectures, design assignments, take/design exams).
2019 Applied Algorithmics (COMP 526) · graduate level
2018 Data Structures and Data Management (CS 240) · undergraduate level
2017 Advanced Algorithmics: Strategies for Hard Problems · advanced graduate 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 graduate 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
graduate 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
Seba stian Wild CV · page 7 of 8
Super vised Student s
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
ESA 2019 · ANALCO 2019 · ANALCO 2018
Review
(journals)
ACM Journal of Experimental Algorithmics · ACM Transactions on Algorithms ·
Algorithmica · Bulletin of Mathematical Biology ·
Combinatorics, Probability & Computing · IEEE Transactions on Computers ·
Information Processing Letters · International Journal of Computer Mathematics ·
Mathematics in Computer Science · Software: Practice and Experience ·
The Computer Journal · Theoretical Computer Science
Review
(conferences)
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
Representative of Scientific Employees in Examination Board · 2012 – 2017
Additional Training
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.
Seba stian Wild CV · page 8 of 8
Languages
German native
English fluent
French elementary
