Publications

Paudice, A., Høgsgaard, M. M., da Cunha, A. & Sun, Y. (2025). Revisiting Agnostic Boosting. In The Thirty-Ninth Annual Conference on Neural Information Processing Systems

Larsen, K. G. & Schalburg, N. (2025). Tight Generalization Bounds for Large-Margin Halfspaces. In The Thirty-ninth Annual Conference on Neural Information Processing Systems https://openreview.net/forum?id=wAq0ZLxrGq

Bringmann, K., Larsen, K. G., Nusser, A., Rotenberg, E. & Wang, Y. (2025). Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. In 41st International Symposium on Computational Geometry (SoCG 2025) (Vol. 332, pp. 25:1-25:16). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2025.25

Larsen, K. G. & Simkin, M. (2025). Time/Space Tradeoffs for Generic Attacks on Delay Functions. In Theory of Cryptography: 23rd International Conference, TCC 2025, Aarhus, Denmark, December 1–5, 2025, Proceedings, Part IV (pp. 451-477). Springer. https://doi.org/10.1007/978-3-032-12290-2_15

Caragiannis, I., Larsen, K. G. & Shyam, S. (2025). A New Lower Bound for Multicolor Discrepancy with Applications to Fair Division. In R. Lavi & J. Zhang (Eds.), Algorithmic Game Theory: 18th International Symposium, SAGT 2025, Bath, UK, September 2–5, 2025, Proceedings (pp. 228-246). Springer. https://doi.org/10.1007/978-3-032-03639-1_13

Afshani, P., Storandt, S. & Bosch, Y. (2025). Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025) (pp. 3:1-3:16). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2025.3

Afshani, P. & Sitchinava , N. (2025). A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM. In ACACM-SIAM Symposium on Discrete Algorithms, SODA 2025 (pp. 3998-4008). Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.136

Høgsgaard, M. M. & Paudice, A. (2025). Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means. In Proceedings of the 42nd International Conference on Machine Learning (Vol. 267, pp. 23357-23381)

Gao, J., Jayaram, R., Kolbe, B., Sapir, S., Schwiegelshohn, C., Silwal, S. & Waingarten, E. (2025). Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures. In Proceedings of the 42nd International Conference on Machine Learning (Vol. 267, pp. 18363-18385)

Høgsgaard, M. M. (2025). Guarantees and Insights in Ensemble Learning. [PhD thesis, Aarhus University].

Schou, J. K. R. (2025). Algorithmic Innovation through Persistence, Topology, and Geometry. [PhD thesis, Aarhus University].

Rysgaard, C. M. (2025). A Journey through Persistence, External Memory, Trees, and other Unrelated Problems. [PhD thesis, Aarhus University].

Burkhardt, J., Keller, H. J., Orlandi, C. & Schwiegelshohn, C. (2025). Distributed Differentially Private Data Analytics via Secure Sketching. In Forty-second International Conference on Machine Learning: ICML 2025 Article 10733 https://openreview.net/forum?id=2Snksn3U47

Midolo, G., Clark, A. T., Chytrý, M., Essl, F., Dullinger, S., Jandt, U., Bruelheide, H., Argagnon, O., Biurrun, I., Chiarucci, A., Ćušterevska, R., De Frenne, P., De Sanctis, M., Dengler, J., Divíšek, J., Dziuba, T., Ejrnæs, R., Garbolino, E., Illa, E. ... Keil, P. (2025). Six Decades of Losses and Gains in Alpha Diversity of European Plant Communities. Ecology Letters, 28(11), Article e70248. https://doi.org/10.1111/ele.70248

Rysgaard, C. M. & Wild, S. (2025). Lazy B-Trees. In P. Gawrychowski, F. Mazowiecki & M. Skrzypczak (Eds.), 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025 Article 87 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2025.87

Brodal, G. S., Iacono, J., Meyer, U., Sitchinava, N., Goodrich, M. T., Lo, J., Pagan, V. & Svenning, R. (2025). External-Memory Priority Queues with Optimal Insertions. In A. Benoit, H. Kaplan, S. Wild, S. Wild & G. Herman (Eds.), 33rd Annual European Symposium on Algorithms, ESA 2025 Article 5 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2025.5

Brodal, G. S., Rysgaard, C. M. & Svenning, R. (2025). Buffered Partially-Persistent External-Memory Search Trees. In A. Benoit, H. Kaplan, S. Wild, S. Wild & G. Herman (Eds.), 33rd Annual European Symposium on Algorithms, ESA 2025 Article 82 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2025.82

Leblanc, C., Bonnet, P., Servajean, M., Thuiller, W., Chytrý, M., Aćić, S., Argagnon, O., Biurrun, I., Bonari, G., Bruelheide, H., Campos, J. A., Čarni, A., Ćušterevska, R., De Sanctis, M., Dengler, J., Dziuba, T., Garbolino, E., Jandt, U., Jansen, F. ... Joly, A. (2025). Learning the syntax of plant assemblages. Nature Plants, 11(10), 2026-2040. https://doi.org/10.1038/s41477-025-02105-7

Di Musciano, M., Zannini, P., Testolin, R., Sabatini, F. M., Santovito, D., Jiménez-Alfaro, B., Jansen, F., Chytrý, M., Ricci, L., Agrillo, E., Attorre, F., Biurrun, I., Bonari, G., Bruun, H. H., Cao Pinna, L., Čarni, A., Carranza, M. L., Cazzolla Gatti, R., Dengler, J. ... Chiarucci, A. (2025). Representativeness of the Natura 2000 network for preserving plant biodiversity in the European Union. Conservation Biology. Advance online publication. https://doi.org/10.1111/cobi.70158

Afshani, P., Buchin, M., Driemel, A., Richter, M. & Wong, S. (2025). Property Testing of Curve Similarity. In A. Benoit, H. Kaplan, S. Wild, S. Wild & G. Herman (Eds.), 33rd Annual European Symposium on Algorithms, ESA 2025 Article 84 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2025.84

Brodal, G. S. (2025). Bottom-up rebalancing binary search trees by flipping a coin. Theoretical Computer Science, 1055, Article 115543. https://doi.org/10.1016/j.tcs.2025.115543

Gündoğar, Z., Ho̷jlund, M. G., Larsen, K. G. & Christiansen, O. (2025). Recursive Linear Tensor Expansion with Natural Occupation Analysis. Journal of Chemical Theory and Computation, 21(19), 9270-9289. https://doi.org/10.1021/acs.jctc.5c01101

Høgsgaard, M. M. & Larsen, K. G. (2025). Improved Margin Generalization Bounds for Voting Classifiers. In Proceedings of Thirty Eighth Conference on Learning Theory (Vol. 291, pp. 2822-2855). PMLR. https://proceedings.mlr.press/v291/hogsgaard-moller25a.html

Brodal, G. S. (2025). A Simple Integer Successor-Delete Data Structure. In P. Mutzel & N. Prezza (Eds.), 23rd International Symposium on Experimental Algorithms, SEA 2025 Article 8 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SEA.2025.8

Cohen-Addad, V., Lattanzi, S. & Schwiegelshohn, C. (2025). Almost Optimal PAC Learning for k-Means. In M. Koucky & N. Bansal (Eds.), STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 2019-2030). Association for Computing Machinery. https://doi.org/10.1145/3717823.3718180

Cohen-Addad, V., Grandoni, F., Lee, E., Schwiegelshohn, C. & Svensson, O. (2025). A (2+ϵ)-Approximation Algorithm for Metric κ-Median. In M. Koucký & N. Bansal (Eds.), STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 615-624). Association for Computing Machinery. https://doi.org/10.1145/3717823.3718299

Afshani, P., Nekrich, Y. & Staals, F. (2025). Convexity Helps Iterated Search in 3D. In O. Aichholzer & H. Wang (Eds.), 41st International Symposium on Computational Geometry, SoCG 2025 Article 3 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2025.3

Karthik, C. S., Lee, E., Rabani, Y., Schwiegelshohn, C. & Zhou, S. (2025). On Approximability of l²₂Min-Sum Clustering. In O. Aichholzer & H. Wang (Eds.), 41st International Symposium on Computational Geometry, SoCG 2025 Article 62 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2025.62

Biniaz, A., Maheshwari, A., Merrild, M. C. R., Mitchell, J. S. B., Odak, S., Polishchuk, V., Robson, E. W., Rysgaard, C. M., Schou, J. K. R., Shermer, T., Spalding-Jamieson, J., Svenning, R. & Zheng, D. W. (2025). Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems. In O. Aichholzer & H. Wang (Eds.), 41st International Symposium on Computational Geometry, SoCG 2025 (pp. 20:1-20:21). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2025.20

Brodal, G. S. (1997). Worst Case Efficient Data Structures. Department of Computer Science, Aarhus University.

Moeslund, J. E. (2012). The role of topography in determining local plant diversity patterns across Denmark. Aarhus University, Faculty of Science and Technology.

Wilkinson, B. T. (2015). Exploring the Problem Space of Orthogonal Range Searching. Department of Computer Science, Aarhus University.

Larsen, K. G. (2013). Models and Techniques for Proving Data Structure Lower Bounds. Department of Computer Science, Aarhus University.

Kejlberg-Rasmussen, C. (2013). Dynamic Data Structures: The Interplay of Invariants and Algorithm Design. Department of Computer Science, Aarhus University.

Brodal, G. S., Lagogiannis, G. & Tarjan, R. E. (2025). Strict Fibonacci Heaps. ACM Transactions on Algorithms, 21(2), Article 15. https://doi.org/10.1145/3707692

Pärtel, M., Tamme, R., Carmona, C. P., Riibak, K., Moora, M., Bennett, J. A., Chiarucci, A., Chytrý, M., de Bello, F., Eriksson, O., Harrison, S., Lewis, R. J., Moles, A. T., Öpik, M., Price, J. N., Amputu, V., Askarizadeh, D., Atashgahi, Z., Aubin, I. ... Zobel, M. (2025). Global impoverishment of natural vegetation revealed by dark diversity. Nature, 641(8064), 917-924. Article e1400253. https://doi.org/10.1038/s41586-025-08814-5

da Cunha, A., Larsen, K. G. & Ritzert, M. (2025). Boosting, Voting Classifiers and Randomized Sample Compression Schemes. In G. Kamath & P. L. Loh (Eds.), Proceedings of Machine Learning Research (Vol. 272, pp. 390-404). MLResearch Press.

Asilis, J., Høgsgaard, M. M. & Velegkas, G. (2025). Understanding Aggregations of Proper Learners in Multiclass Classification. In Proceedings of The 36th International Conference on Algorithmic Learning Theory (pp. 89-111). PMLR.

Høgsgaard, M. M. (2025). Efficient Optimal PAC Learning. In Proceedings of The 36th International Conference on Algorithmic Learning Theory (pp. 578-580). PMLR.

Assmann, J. J., Pedersen, P. B. M., Moeslund, J. E., Senf, C., Treier, U. A., Corcoran, D., Koma, Z., Nord-Larsen, T. & Normand, S. (2025). Temperate forests of high conservation value are successfully identified by satellite and LiDAR data fusion. Conservation Science and Practice, 7(2), Article e13302. https://doi.org/10.1111/csp2.13302

Cohen-Addad, V., Draganov, A., Russo, M., Saulpic, D. & Schwiegelshohn, C. (2025). A Tight VC-Dimension Analysis of Clustering Coresets with Applications. In Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 (pp. 4783-4808). Association for Computing Machinery.

Brodal, G. S. & Rysgaard, C. M. (2025). Pure Binary Finger Search Trees. In I.-O. Bercea & R. Pagh (Eds.), 8th SIAM Symposium on Simplicity of Algorithms, SOSA 2025 (pp. 172-195). Society for Industrial and Applied Mathematics.

Brewer, B., Brodal, G. S. & Wang, H. (2025). Dynamic Convex Hulls for Simple Paths. Discrete and Computational Geometry. Advance online publication. https://doi.org/10.1007/s00454-024-00715-0

Yu, H., Larsen, K. G. & Christiansen, O. (2025). Optimization methods for tensor decomposition: A comparison of new algorithms for fitting the CP(CANDECOMP/PARAFAC) model. Chemometrics and Intelligent Laboratory Systems, 257, Article 105290. https://doi.org/10.1016/j.chemolab.2024.105290

Zhivotovskiy, N., Larsen, K. G. & Montasser, O. (2024). Derandomizing Multi-Distribution Learning. Abstract from NeurIPS'24: 38th Conference on Neural Information Processing Systems, Vancouver, Canada.

da Cunha, A., Høgsgaard, M. M. & Larsen, K. G. (2024). Optimal Parallelization of Boosting. Abstract from NeurIPS'24: 38th Conference on Neural Information Processing Systems, Vancouver, Canada.

Afshani, P., Killmann, R. & Larsen, K. G. (2024). Hierarchical categories in colored searching. Computational Geometry, 121, Article 102090. https://doi.org/10.1016/j.comgeo.2024.102090

Alon, N., Bousquet, O., Larsen, K. G., Moran, S. & Moran, S. (2024). Diagonalization Games. The American Mathematical Monthly, 131(10), 866-879. https://doi.org/10.1080/00029890.2024.2393992

Hanneke, S., Larsen, K. G. & Zhivotovskiy, N. (2024). Revisiting Agnostic PAC Learning. In Proceedings - 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, FOCS 2024 (pp. 1968-1982). IEEE. https://doi.org/10.1109/FOCS61266.2024.00118

Kalavasis, A., Karbasi, A., Larsen, K. G., Velegkas, G. & Zhou, F. (2024). Replicable Learning of Large-Margin Halfspaces. In Proceedings of the 41 st International Conference on Machine Learning (Vol. 235, pp. 22861-22878). MLResearch Press.

Displaying results 1 to 50 out of 451

Revised 01.09.2025

Publications

Head of research