Dr Sebastian Wild

Senior Lecturer Computer Science

+44 (0)151 795 4243 Ext. 54243
Work email Sebastian.Wild@liverpool.ac.uk
Personal Websitehttps://www.wild-inter.net

Publications

Selected Publications

Randomized Communication and Implicit Graph Representations (Conference Paper - 2022)
Lazy Search Trees (Conference Paper - 2021)
Hypersuccinct Trees - New universal tree source codes for optimal compressed tree data structures and range minima (Conference Paper - 2021)
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs (Conference Paper - 2018)

Filter the publication list

Filter list by type

Show all
Journal article
Conference paper
Chapter
Other

2024

Deterministic Cache-Oblivious Funnelselect (Conference Paper)

Brodal, G. S., & Wild, S. (2024). Deterministic Cache-Oblivious Funnelselect. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 294. doi:10.4230/LIPIcs.SWAT.2024.17

DOI: 10.4230/LIPIcs.SWAT.2024.17

Polyamorous Scheduling (Conference Paper)

Gąsieniec, L., Smith, B., & Wild, S. (2024). Polyamorous Scheduling. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 291. doi:10.4230/LIPIcs.FUN.2024.15

DOI: 10.4230/LIPIcs.FUN.2024.15

Towards Optimal Grammars for RNA Structures (Conference Paper)

Onokpasa, E., Wild, S., & Wong, P. W. H. (2024). Towards Optimal Grammars for RNA Structures. In 2024 Data Compression Conference (DCC). IEEE. doi:10.1109/dcc58796.2024.00041

DOI: 10.1109/dcc58796.2024.00041

Polyamorous Scheduling (Preprint)

Deterministic Cache-Oblivious Funnelselect (Preprint)

Towards Optimal Grammars for RNA Structures (Preprint)

An Optimal Randomized Algorithm for Finding the Saddlepoint (Preprint)

Finding the saddlepoint faster than sorting (Chapter)

Dallant, J., Haagensen, F., Jacob, R., Kozma, L., & Wild, S. (2024). Finding the saddlepoint faster than sorting. In 2024 Symposium on Simplicity in Algorithms (SOSA) (pp. 168-178). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977936.17

DOI: 10.1137/1.9781611977936.17

Polyamorous Scheduling. (Preprint)

2023

Finding the saddlepoint faster than sorting (Preprint)

Funnelselect: Cache-Oblivious Multiple Selection (Conference Paper)

Brodal, G. S., & Wild, S. (2023). Funnelselect: Cache-Oblivious Multiple Selection. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 274. doi:10.4230/LIPIcs.ESA.2023.25

DOI: 10.4230/LIPIcs.ESA.2023.25

A House Divided: Cooperation, Polarization, and the Power of Reputation (Report)

Fekete, S., Wild, S., Keldenich, P., Spiess, J., Schlund, M., Costard, J., . . . Stursberg, P. (2023). A House Divided: Cooperation, Polarization, and the Power of Reputation: Research Square Platform LLC. doi:10.21203/rs.3.rs-3117463/v1

DOI: 10.21203/rs.3.rs-3117463/v1

A simple and fast linear-time algorithm for divisor methods of apportionment (Journal article)

Reitzig, R., & Wild, S. (2023). A simple and fast linear-time algorithm for divisor methods of apportionment. Mathematical Programming. doi:10.1007/s10107-023-01929-5

DOI: 10.1007/s10107-023-01929-5

Succinct Permutation Graphs (Journal article)

Tsakalidis, K., Wild, S., & Zamaraev, V. (n.d.). Succinct Permutation Graphs. Algorithmica. doi:10.1007/s00453-022-01039-2

DOI: 10.1007/s00453-022-01039-2

Multiway Powersort (Conference Paper)

Gelling, W. C., Nebel, M. E., Smith, B., & Wild, S. (2023). Multiway Powersort. In Proceedings of the Workshop on Algorithm Engineering and Experiments Vol. 2023-January (pp. 190-200).

RNA secondary structures: from ab initio prediction to better compression, and back (Conference Paper)

Onokpasa, E., Wild, S., & Wong, P. W. H. (2023). RNA secondary structures: from ab initio prediction to better compression, and back. In 2023 DATA COMPRESSION CONFERENCE, DCC (pp. 278-287). doi:10.1109/DCC55655.2023.00036

DOI: 10.1109/DCC55655.2023.00036

2022

Randomized Communication and Implicit Graph Representations (Conference Paper)

Harms, N., Wild, S., & Zamaraev, V. (2022). Randomized Communication and Implicit Graph Representations. In PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) (pp. 1220-1233). doi:10.1145/3519935.3519978

DOI: 10.1145/3519935.3519978

Towards the 5/6-Density Conjecture of Pinwheel Scheduling. (Conference Paper)

Gasieniec, L., Smith, B., & Wild, S. (2022). Towards the 5/6-Density Conjecture of Pinwheel Scheduling.. In C. A. Phillips, & B. Speckmann (Eds.), ALENEX (pp. 91-103). SIAM. Retrieved from https://doi.org/10.1137/1.9781611977042

2021

Randomized Communication and Implicit Graph Representations (Preprint)

DOI: 10.48550/arxiv.2111.03639

Towards the 5/6-Density Conjecture of Pinwheel Scheduling (Conference Paper)

Gąsieniec, L., Smith, B., & Wild, S. (2021). Towards the 5/6-Density Conjecture of Pinwheel Scheduling. Retrieved from http://arxiv.org/abs/2111.01784v1

Towards the 5/6-Density Conjecture of Pinwheel Scheduling. (Preprint)

Succinct Euler-Tour Trees (Conference Paper)

Gagie, T., & Wild, S. (2021). Succinct Euler-Tour Trees. Retrieved from http://arxiv.org/abs/2105.04965v2

Hypersuccinct Trees - New universal tree source codes for optimal compressed tree data structures and range minima (Conference Paper)

Munro, J. I., Nicholson, P. K., Benkner, L. S., & Wild, S. (2021). Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima. Retrieved from http://dx.doi.org/10.4230/LIPIcs.ESA.2021.70

DOI: 10.4230/LIPIcs.ESA.2021.70

Lazy Search Trees (Conference Paper)

Sandlund, B., & Wild, S. (2021). Lazy Search Trees. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS Vol. 2020 (pp. 704-715). Virtual Conference: IEEE Computer Society Press. doi:10.1109/FOCS46700.2020.00071

DOI: 10.1109/FOCS46700.2020.00071

Randomized Communication and the Implicit Graph Conjecture. (Preprint)

Succinct Euler-Tour Trees (Conference Paper)

Gagie, T., & Wild, S. (2021). Succinct Euler-Tour Trees. In Proceedings of the 33rd Canadian Conference on Computational Geometry, CCCG 2021 (pp. 368-376).

2020

Distance oracles for interval graphs via breadth-first rank/select in succinct trees (Conference Paper)

He, M., Ian Munro, J., Nekrich, Y., Wild, S., & Wu, K. (2020). Distance oracles for interval graphs via breadth-first rank/select in succinct trees. In Leibniz International Proceedings in Informatics, LIPIcs Vol. 181 (pp. 251-2518). doi:10.4230/LIPIcs.ISAAC.2020.25

DOI: 10.4230/LIPIcs.ISAAC.2020.25

Lazy Search Trees (Preprint)

DOI: 10.48550/arxiv.2010.08840

Succinct Permutation Graphs (Report)

Tsakalidis, K., Wild, S., & Zamaraev, V. (2020). Succinct Permutation Graphs. Retrieved from http://dx.doi.org/10.1007/s00453-022-01039-2

Succinct Permutation Graphs (Preprint)

DOI: 10.48550/arxiv.2010.04108

Lazy Search Trees (Conference Paper)

Sandlund, B., & Wild, S. (n.d.). Lazy Search Trees. Retrieved from http://arxiv.org/abs/2010.08840v1

QuickXsort: A Fast Sorting Scheme in Theory and Practice (Journal article)

Edelkamp, S., Weiß, A., & Wild, S. (2020). QuickXsort: A Fast Sorting Scheme in Theory and Practice. Algorithmica: an international journal in computer science, 82, 509-588. doi:10.1007/s00453-019-00634-0

DOI: 10.1007/s00453-019-00634-0

2019

Dynamic Optimality Refuted -- For Tournament Heaps (Report)

Munro, J. I., Peng, R., Wild, S., & Zhang, L. (2019). Dynamic Optimality Refuted -- For Tournament Heaps. Retrieved from http://arxiv.org/abs/1908.00563v1

Efficient Second-Order Shape-Constrained Function Fitting (Conference Paper)

Durfee, D., Gao, Y., Rao, A. B., & Wild, S. (2019). Efficient Second-Order Shape-Constrained Function Fitting. In ALGORITHMS AND DATA STRUCTURES, WADS 2019 Vol. 11646 (pp. 395-408). doi:10.1007/978-3-030-24766-9_29

DOI: 10.1007/978-3-030-24766-9_29

Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space (Report)

Munro, J. I., & Wild, S. (2019). Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space. Retrieved from http://arxiv.org/abs/1903.02533v1

Efficient Second-Order Shape-Constrained Function Fitting (Conference Paper)

Durfee, D., Gao, Y., Rao, A. B., & Wild, S. (2019). Efficient Second-Order Shape-Constrained Function Fitting. In Unknown Conference Vol. 11646 (pp. 395-408). Springer Nature. doi:10.1007/978-3-030-24766-9_29

DOI: 10.1007/978-3-030-24766-9_29

2018

QuickXsort - A Fast Sorting Scheme in Theory and Practice (Preprint)

DOI: 10.48550/arxiv.1811.01259

QuickXsort: A Fast Sorting Scheme in Theory and Practice (Journal article)

Edelkamp, S., Weiss, A., & Wild, S. (2020). QuickXsort: A Fast Sorting Scheme in Theory and Practice. ALGORITHMICA, 82(3), 509-588. doi:10.1007/s00453-019-00634-0

DOI: 10.1007/s00453-019-00634-0

Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks (Journal article)

Reitzig, R., & Wild, S. (2018). Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks. Algorithmica: an international journal in computer science, 80(11), 3365-3396. doi:10.1007/s00453-017-0392-3

DOI: 10.1007/s00453-017-0392-3

Sesquickselect: One and a half pivots for cache-efficient selection (Conference Paper)

Martínez, C., Nebel, M., & Wild, S. (2018). Sesquickselect: One and a half pivots for cache-efficient selection. Retrieved from http://dx.doi.org/10.1137/1.9781611975505.6

Dual-pivot and beyond: The potential of multiway partitioning in quicksort (Journal article)

Wild, S. (2018). Dual-pivot and beyond: The potential of multiway partitioning in quicksort. IT-INFORMATION TECHNOLOGY, 60(3), 173-177. doi:10.1515/itit-2018-0012

DOI: 10.1515/itit-2018-0012

Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs (Conference Paper)

Munro, J. I., & Wild, S. (2018). Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. Retrieved from http://dx.doi.org/10.4230/lipics.esa.2018.63

Entwurf und Analyse von Algorithmen (Book)

Nebel, M., & Wild, S. (2018). Entwurf und Analyse von Algorithmen. Springer Fachmedien Wiesbaden. doi:10.1007/978-3-658-21155-4

DOI: 10.1007/978-3-658-21155-4

Average Cost of QuickXsort with Pivot Sampling (Conference Paper)

Wild, S. (2018). Average Cost of QuickXsort with Pivot Sampling. Retrieved from http://dx.doi.org/10.4230/lipics.aofa.2018.36

2016

Median-of-k Jumplists and Dangling-Min BSTs (Conference Paper)

Nebel, M. E., Neumann, E., & Wild, S. (2016). Median-of-k Jumplists and Dangling-Min BSTs. Retrieved from http://dx.doi.org/10.1137/1.9781611975505.8

Median-of-k Jumplists and Dangling-Min BSTs (Preprint)

DOI: 10.48550/arxiv.1609.08513

Quicksort Is Optimal For Many Equal Keys (Conference Paper)

Wild, S. (2016). Quicksort Is Optimal For Many Equal Keys. Retrieved from http://dx.doi.org/10.1137/1.9781611975062.2

2015

Why Is Dual-Pivot Quicksort Fast? (Other)

Wild, S. (2015). Why Is Dual-Pivot Quicksort Fast?. Retrieved from http://arxiv.org/abs/1511.01138v2

A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment (Report)

Reitzig, R., & Wild, S. (2015). A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment. Retrieved from http://arxiv.org/abs/1504.06475v4

A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment (Preprint)

DOI: 10.48550/arxiv.1504.06475

Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (Preprint)

DOI: 10.48550/arxiv.1502.04048

2014

Analysis of Pivot Sampling in Dual-Pivot Quicksort (Preprint)

DOI: 10.48550/arxiv.1412.0193

Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy's Partitioning Scheme (Journal article)

Nebel, M. E., Wild, S., & Martinez, C. (2016). Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy's Partitioning Scheme. Algorithmica: an international journal in computer science, 75(4), 632-683. doi:10.1007/s00453-015-0041-7

DOI: 10.1007/s00453-015-0041-7

Analysis of Branch Misses in Quicksort (Conference Paper)

Martínez, C., Nebel, M. E., & Wild, S. (2014). Analysis of Branch Misses in Quicksort. Retrieved from http://dx.doi.org/10.1137/1.9781611973761.11

Analysis of Branch Misses in Quicksort (Preprint)

DOI: 10.48550/arxiv.1411.2059

Pivot Sampling in Dual-Pivot Quicksort (Preprint)

DOI: 10.48550/arxiv.1403.6602

Pivot Sampling in Dual-Pivot Quicksort (Conference Paper)

Nebel, M. E., & Wild, S. (2014). Pivot Sampling in Dual-Pivot Quicksort. Retrieved from http://arxiv.org/abs/1403.6602v2

2013

Average Case Analysis of Java 7's Dual Pivot Quicksort (Preprint)

DOI: 10.48550/arxiv.1310.7409

Average Case Analysis of Java 7's Dual Pivot Quicksort (Conference Paper)

Wild, S., & Nebel, M. E. (2012). Average Case Analysis of Java 7's Dual Pivot Quicksort. In ALGORITHMS - ESA 2012 Vol. 7501 (pp. 825-836). Retrieved from https://www.webofscience.com/

Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm (Journal article)

Wild, S., Nebel, M. E., & Mahmoud, H. (2016). Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm. Algorithmica: an international journal in computer science, 74(1), 485-506. doi:10.1007/s00453-014-9953-x

DOI: 10.1007/s00453-014-9953-x

Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm (Preprint)

DOI: 10.48550/arxiv.1306.3819

Average Case and Distributional Analysis of Dual-Pivot Quicksort (Journal article)

Wild, S., Nebel, M. E., & Neininger, R. (2015). Average Case and Distributional Analysis of Dual-Pivot Quicksort. ACM Transactions on Algorithms, 11(3). doi:10.1145/2629340

DOI: 10.1145/2629340

Average Case and Distributional Analysis of Dual-Pivot Quicksort (Preprint)

DOI: 10.48550/arxiv.1304.0988

Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn (Conference Paper)

Wild, S., Nebel, M., Reitzig, R., & Laube, U. (2013). Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn. In Unknown Conference (pp. 55-69). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611972931.5

DOI: 10.1137/1.9781611972931.5

2012

Average Case Analysis of Java 7’s Dual Pivot Quicksort (Chapter)

Wild, S., & Nebel, M. E. (2012). Average Case Analysis of Java 7’s Dual Pivot Quicksort. In Algorithms – ESA 2012 (Vol. 7501, pp. 825-836). Springer Nature. doi:10.1007/978-3-642-33090-2_71

DOI: 10.1007/978-3-642-33090-2_71

2011

JAGUC - A SOFTWARE PACKAGE FOR ENVIRONMENTAL DIVERSITY ANALYSES (Journal article)

Nebel, M. E., Wild, S., Holzhauser, M., Huettenberger, L., Reitzig, R., Sperber, M., & Stoeck, T. (2011). JAGUC - A SOFTWARE PACKAGE FOR ENVIRONMENTAL DIVERSITY ANALYSES. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, 9(6), 749-773. doi:10.1142/S0219720011005781

DOI: 10.1142/S0219720011005781