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)
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 Leibniz International Proceedings in Informatics, LIPIcs Vol. 308. doi:10.4230/LIPIcs.ESA.2024.44
Preface
Mailler, C., & Wild, S. (2024). Preface. Leibniz International Proceedings in Informatics, LIPIcs, 302.
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 2024 Symposium on Simplicity in Algorithms (SOSA) (pp. 168-178). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611977936.17
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: Research Square Platform 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. (n.d.). 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 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
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
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.
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
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
Succinct Euler-Tour Trees
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
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
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
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., 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
Lazy Search Trees
Succinct Permutation Graphs
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., 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
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
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 Lecture Notes in Computer Science Vol. 11646 (pp. 395-408). Springer Nature. doi:10.1007/978-3-030-24766-9_29
2018
QuickXsort - A Fast Sorting Scheme in Theory and Practice
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
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
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
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
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. Retrieved from http://dx.doi.org/10.4230/lipics.esa.2018.63
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
Average Cost of QuickXsort with Pivot Sampling
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
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
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
2015
Why Is Dual-Pivot Quicksort Fast?
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
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
Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
2014
Analysis of Pivot Sampling in Dual-Pivot Quicksort
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 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
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
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/
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
Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Average Case and Distributional Analysis of Dual-Pivot Quicksort
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
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). 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