Research outputs
Selected research outputs
- 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)
2026
Succinct Preferential-Attachment Graphs
Ismaili Alaoui, Z., Namrata., & Wild, S. (2026). Succinct Preferential-Attachment Graphs. In Lecture Notes in Computer Science (pp. 270-285). Springer Nature Switzerland. doi:10.1007/978-3-032-11835-6_20
2025
Randomized Communication and Implicit Graph Representations
Harms, N., Wild, S., & Zamaraev, V. (2025). Randomized Communication and Implicit Graph Representations. TheoretiCS, Volume 4. doi:10.46298/theoretics.25.20
Lazy B-Trees
Rysgaard, C. M., & Wild, S. (2025). Lazy B-Trees. In Leibniz International Proceedings in Informatics Lipics Vol. 345. doi:10.4230/LIPIcs.MFCS.2025.87
Adaptive sorting for large keys, strings, and database rows
Marius, K., Bernhard, S., Wild, S., & Goetz, G. (2025). Adaptive sorting for large keys, strings, and database rows. In Datenbanksysteme für Business, Technologie und Web (BTW 2025). Gesellschaft für Informatik, Bonn. doi:10.18420/BTW2025-10
Simple approximation algorithms for Polyamorous Scheduling
Biktairov, Y., Gąsieniec, L., Jiamjitrak, W. P., Namrata., Smith, B., & Wild, S. (2025). Simple approximation algorithms for Polyamorous Scheduling. In 8th SIAM Symposium on Simplicity of Algorithms Sosa 2025 (pp. 290-314).
2024
An Optimal Randomized Algorithm for Finding the Saddlepoint
Dallant, J., Haagensen, F., Jacob, R., Kozma, L., & Wild, S. (2024). An Optimal Randomized Algorithm for Finding the Saddlepoint. In 32ND ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS, ESA 2024 Vol. 308. doi:10.4230/LIPIcs.ESA.2024.44
Deterministic Cache-Oblivious Funnelselect
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
Polyamorous Scheduling
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
Towards Optimal Grammars for RNA Structures
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
Finding the saddlepoint faster than sorting
Dallant, J., Haagensen, F., Jacob, R., Kozma, L., & Wild, S. (2024). Finding the saddlepoint faster than sorting. In Unknown Book (pp. 168-178). Retrieved from https://www.webofscience.com/
2023
Funnelselect: Cache-Oblivious Multiple Selection
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
A House Divided: Cooperation, Polarization, and the Power of Reputation
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: Springer Science and Business Media LLC. doi:10.21203/rs.3.rs-3117463/v1
A simple and fast linear-time algorithm for divisor methods of apportionment
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
Succinct Permutation Graphs
Tsakalidis, K., Wild, S., & Zamaraev, V. (2022). Succinct Permutation Graphs. Algorithmica. doi:10.1007/s00453-022-01039-2
Multiway Powersort
Gelling, W. C., Nebel, M. E., Smith, B., & Wild, S. (2023). Multiway Powersort. In 2023 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX (pp. 190-200). Retrieved from https://www.webofscience.com/
RNA secondary structures: from ab initio prediction to better compression, and back
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
2022
Succinct Permutation Graphs
Randomized Communication and Implicit Graph Representations
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
Towards the 5/6-Density Conjecture of Pinwheel Scheduling
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
Gasieniec, L., Smiths, B., & Wild, S. (2022). Towards the 5/6-Density Conjecture of Pinwheel Scheduling. In 2022 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX (pp. 91-103). Retrieved from https://www.webofscience.com/
2021
Hypersuccinct Trees - New universal tree source codes for optimal compressed tree data structures and range minima
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
Succinct Euler-Tour Trees
Gagie, T., & Wild, S. (2021). Succinct Euler-Tour Trees. Retrieved from http://arxiv.org/abs/2105.04965v2
Lazy Search Trees
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
Dual-pivot and beyond: The potential of multiway partitioning in quicksort
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
Succinct Euler-Tour Trees
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
He, M., Munro, J. I., Nekrich, Y., Wild, S., & Wu, K. (2020). Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. In 31ST INTERNATIONAL SYMPOSIUM ON ALGORITHMS AND COMPUTATION, ISAAC 2020 Vol. 181. doi:10.4230/LIPIcs.ISAAC.2020.25
Lazy Search Trees
Succinct Permutation Graphs
Tsakalidis, K., Wild, S., & Zamaraev, V. (2020). Succinct Permutation Graphs. Retrieved from http://dx.doi.org/10.1007/s00453-022-01039-2
Lazy Search Trees
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
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
QuickXsort: A Fast Sorting Scheme in Theory and Practice
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
2019
Dynamic Optimality Refuted -- For Tournament Heaps
Munro, J. I., Peng, R., Wild, S., & Zhang, L. (2019). Dynamic Optimality Refuted -- For Tournament Heaps. Retrieved from http://arxiv.org/abs/1908.00563v1
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
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
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
Efficient Second-Order Shape-Constrained Function Fitting
Durfee, D., Gao, Y., Rao, A. B., & Wild, S. (2019). Efficient Second-Order Shape-Constrained Function Fitting. In Lecture Notes in Computer Science Vol. 11646 (pp. 395-408). Springer Nature. doi:10.1007/978-3-030-24766-9_29
Median-of-k Jumplists and Dangling-Min BSTs
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
Sesquickselect: One and a half pivots for cache-efficient selection
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
2018
QuickXsort - A Fast Sorting Scheme in Theory and Practice
Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks
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
Median-of-k Jumplists and Dangling-Min BSTs
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
Munro, J. I., & Wild, S. (2018). Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. In 26TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS, ESA 2018 Vol. 112. doi:10.4230/LIPIcs.ESA.2018.63
Average Cost of QuickXsort with Pivot Sampling
Wild, S. (2018). Average Cost of QuickXsort with Pivot Sampling. In 29TH INTERNATIONAL CONFERENCE ON PROBABILISTIC, COMBINATORIAL AND ASYMPTOTIC METHODS FOR THE ANALYSIS OF ALGORITHMS, AOFA 2018 Vol. 110. doi:10.4230/LIPIcs.AofA.2018.36
Entwurf und Analyse von Algorithmen
Nebel, M., & Wild, S. (2018). Entwurf und Analyse von Algorithmen. Springer Fachmedien Wiesbaden. doi:10.1007/978-3-658-21155-4
Quicksort Is Optimal For Many Equal Keys
Wild, S. (2016). Quicksort Is Optimal For Many Equal Keys. Retrieved from http://dx.doi.org/10.1137/1.9781611975062.2
2017
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
2016
Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy's Partitioning Scheme
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
Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm
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
2015
Why Is Dual-Pivot Quicksort Fast?
Wild, S. (2015). Why Is Dual-Pivot Quicksort Fast?. Retrieved from http://arxiv.org/abs/1511.01138v2
Analysis of Pivot Sampling in Dual-Pivot Quicksort
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
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
Average Case and Distributional Analysis of Dual-Pivot Quicksort
Analysis of Branch Misses in Quicksort
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
Average Case and Distributional Analysis of Dual-Pivot Quicksort
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
2014
Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Analysis of Branch Misses in Quicksort
Pivot Sampling in Dual-Pivot Quicksort
Pivot Sampling in Dual-Pivot Quicksort
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
Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn
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
2012
Average Case Analysis of Java 7's Dual Pivot Quicksort
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/
Average Case Analysis of Java 7’s Dual Pivot Quicksort
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
2011
JAGUC - A SOFTWARE PACKAGE FOR ENVIRONMENTAL DIVERSITY ANALYSES
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