Department of Computer Science

Aarhus University Seal
 Department of Computer Science Research Publications

Publications

Sort by: Date
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. & 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
Rysgaard, C. M. (2025). A Journey through Persistence, External Memory, Trees, and other Unrelated Problems. [PhD thesis, Aarhus University].
Schou, J. K. R. (2025). Algorithmic Innovation through Persistence, Topology, and Geometry. [PhD thesis, Aarhus University].
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
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
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
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., 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.
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.
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
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
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., 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
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
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
Høgsgaard, M. M. (2025). Efficient Optimal PAC Learning. In Proceedings of The 36th International Conference on Algorithmic Learning Theory (pp. 578-580). PMLR.
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
Hähn, G. J. A., Damasceno, G., Alvarez-Davila, E., Aubin, I., Bauters, M., Bergmeier, E., Biurrun, I., Bjorkman, A. D., Bonari, G., Botta-Dukát, Z., Campos, J. A., Čarni, A., Chytrý, M., Ćušterevska, R., de Gasper, A. L., De Sanctis, M., Dengler, J., Dolezal, J., El-Sheikh, M. A. ... Bruelheide, H. (2025). Global decoupling of functional and phylogenetic diversity in plant communities. Nature Ecology and Evolution, 9(2), 237-248. Article e12976. https://doi.org/10.1038/s41559-024-02589-0
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
Høgsgaard, M. M. (2025). Guarantees and Insights in Ensemble Learning. [PhD thesis, Aarhus University].
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
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
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
Karthik, C. S., Lee, E., Rabani, Y., Schwiegelshohn, C. & Zhou, S. (2025). On Approximability of l22Min-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
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
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
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. & 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.
Sølvsten, S., Rysgaard, C. M. & van de Pol, J. (2025). Random Access on Narrow Decision Diagrams in External Memory. In T. Neele & A. Wijs (Eds.), Model Checking Software: 30th International Symposium, SPIN 2024, Luxembourg City, Luxembourg, April 8–9, 2024, Proceedings (pp. 137–145). Springer. https://doi.org/10.1007/978-3-031-66149-5_7
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)
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
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
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
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
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
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
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
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
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. & 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)
Leblanc, C., Bonnet, P., Servajean, M., Chytrý, M., Aćić, S., Argagnon, O., Bergamini, A., Biurrun, I., Bonari, G., Campos, J. A., Čarni, A., Ćušterevska, R., De Sanctis, M., Dengler, J., Garbolino, E., Golub, V., Jandt, U., Jansen, F., Lebedeva, M. ... Joly, A. (2024). A deep-learning framework for enhancing habitat identification based on species composition. Applied Vegetation Science, 27(3), Article e12802. https://doi.org/10.1111/avsc.12802
Larsen, K. G. (2024). Bagging is an Optimal PAC Learner (Extended Abstract). In K. Larson (Ed.), Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) (pp. 8411-8415). IJCAI Organization. https://doi.org/10.24963/ijcai.2024/932
Brodal, G. S. (2024). Bottom-Up Rebalancing Binary Search Trees by Flipping a Coin. In A. Z. Broder & T. Tamir (Eds.), 12th International Conference on Fun with Algorithms, FUN 2024 Article 6 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FUN.2024.6
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.
Brodal, G. S. & Wild, S. (2024). Deterministic Cache-Oblivious Funnelselect. In H. L. Bodlaender (Ed.), 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 Article 17 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SWAT.2024.17
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
Brewer, B., Brodal, G. S. & Wang, H. (2024). Dynamic Convex Hulls for Simple Paths. In W. Mulzer & J. M. Phillips (Eds.), 40th International Symposium on Computational Geometry, SoCG 2024 Article 24 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2024.24
Larsen, K. G. (2024). From TCS to Learning Theory. In R. Kralovic & A. Kucera (Eds.), 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 Article 4 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2024.4
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

Displaying results 1 to 50 out of 451

1

2

3

4

5

6

7

8

9

10

Next

Head of research

Revised 01.09.2025