Publications

Larsen, K. G. & Simkin, M. (2020). Secret sharing lower bound: Either reconstruction is hard or shares are long. In C. Galdi & V. Kolesnikov (Eds.), Security and Cryptography for Networks (pp. 566-578). Springer. https://doi.org/10.1007/978-3-030-57990-6_28

Larsen, K. G., Simkin, M. & Yeo, K. (2020). Lower Bounds for Multi-server Oblivious RAMs. In R. Pass & K. Pietrzak (Eds.), Theory of Cryptography - 18th International Conference, TCC 2020, Proceedings (pp. 486-503). Springer. https://doi.org/10.1007/978-3-030-64375-1_17

Larsen, K. G., Starup, J. L. & Steensgaard, J. (2021). Further Unifying the Landscape of Cell Probe Lower Bounds. 224-231. Paper presented at Happening virtually , -. https://cs.au.dk/~larsen/papers/FurtherUnifying.pdf

Larsen, K. G., Pagh, R. & Tetek, J. (2021). CountSketches, Feature Hashing and the Median of Three. In M. Meila & T. Zhang (Eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021 (pp. 6011-6020) http://proceedings.mlr.press/v139/larsen21a.html

Larsen, K. G. & Ritzert, M. (2022). Optimal Weak to Strong Learning. arxiv.org. https://doi.org/10.48550/arXiv.2206.01563

Larsen, K. G., Obremski, M. & Simkin, M. (2023). Distributed Shuffling in Adversarial Environments. In K.-M. Chung (Ed.), 4th Conference on Information-Theoretic Cryptography, ITC 2023 Article 10 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITC.2023.10

Larsen, K. G. (2023). Bagging is an Optimal PAC Learner. In G. Neu & L. Rosasco (Eds.), Proceedings of COLT 2023 (Vol. 195, pp. 450-468). MLResearch Press.

Larsen, K. G. (2023). Fast Discrepancy Minimization with Hereditary Guarantees. In N. Bansal & V. Nagarajan (Eds.), Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 276-289). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch11

Larsen, K. G., Pagh, R., Persiano, G., Pitassi, T., Yeo, K. & Zamir, O. (2024). Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. In K. Bringmann, M. Grohe, G. Puppis & O. Svensson (Eds.), 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 Article 104 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2024.104

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

Larsen, K. G. & Yu, H. (2023). Super-Logarithmic Lower Bounds for Dynamic Graph Problems. In Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 (pp. 1589-1604). IEEE. https://doi.org/10.1109/FOCS57990.2023.00096

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

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

Larsen, K. G. & Simkin, M. (2026). Time/Space Tradeoffs for Generic Attacks on Delay Functions. In B. Applebaum & H. Lin (Eds.), 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

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. & Yu, H. (2026). SUPER-LOGARITHMIC LOWER BOUNDS FOR DYNAMIC GRAPH PROBLEMS. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (3 ed., Vol. 55, pp. FOCS23-42-FOCS23-69) https://doi.org/10.1137/24M1638215

Kutz, M., Brodal, G. S., Kaligosi, K. & Katriel, I. (2011). Faster Algorithms for Computing Longest Common Increasing Subsequences. Journal of Discrete Algorithms, 9(4), 314-325. https://doi.org/10.1016/j.jda.2011.03.013

Knollová, I., Chytrý, M., Bruelheide, H., Dullinger, S., Jandt, U., Bernhardt-Römermann, M., Biurrun, I., de Bello, F., Glaser, M., Hennekens, S., Jansen, F., Jiménez-Alfaro, B., Kadaš, D., Kaplan, E., Klinkovská, K., Lenzner, B., Pauli, H., Sperandii, M. G., Verheyen, K. ... Essl, F. (2024). ReSurveyEurope: A database of resurveyed vegetation plots in Europe. Journal of Vegetation Science, 35(2), Article e13235. https://doi.org/10.1111/jvs.13235

Kejlberg-Rasmussen, C. & Brodal, G. S. (2012). Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property. Leibniz International Proceedings in Informatics, 14, 112--123. https://doi.org/10.4230/LIPIcs.STACS.2012.112

Kejlberg-Rasmussen, C., Tsakalidis, K. & Tsichlas, K. (2012). I/O-Efficient Dynamic Planar Range Skyline Queries. arxiv.org. http://arxiv.org/abs/1207.2341

Kejlberg-Rasmussen, C., Tao, Y., Tsakalidis, K., Tsichlas, K. & Yoon, J. (2013). I/O-Efficient Planar Range Skyline and Attrition Priority Queues. In R. Hull & W. Fan (Eds.), Proceedings of the 32nd symposium on Principles of database systems , PODS '13 (pp. 103-114 ). Association for Computing Machinery. https://doi.org/10.1145/2463664.2465225

Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S. & Porat, E. (2014). Word-packing Algorithms for Dynamic Connectivity and Dynamic Sets. (1407.6755v1 ed.) arxiv.org. http://arxiv.org/abs/1407.6755v1

Kejlberg-Rasmussen, C., Tao, Y., Tsakalidis, K., Tsichlas, K. & Yoon, J. (2021). I/O-efficient 2-d orthogonal range skyline and attrition priority queues. Computational Geometry: Theory and Applications, 93, Article 101689. https://doi.org/10.1016/j.comgeo.2020.101689

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

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

Karbasi, A. & Larsen, K. G. (2024). The Impossibility of Parallelizing Boosting. In Proceedings of Machine Learning Research (Vol. 237, pp. 635-653)

Kambach, S., Sabatini, F. M., Attorre, F., Biurrun, I., Boenisch, G., Bonari, G., Čarni, A., Carranza, M. L., Chiarucci, A., Chytrý, M., Dengler, J., Garbolino, E., Golub, V., Güler, B., Jandt, U., Jansen, J., Jašková, A., Jiménez-Alfaro, B., Karger, D. N. ... Bruelheide, H. (2023). Climate-trait relationships exhibit strong habitat specificity in plant communities across Europe. Nature Communications, 14(1), Article 712. https://doi.org/10.1038/s41467-023-36240-6

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.

Jørgensen, A. G., Brodal, G. S., Moruz, G., Mølhave, T., Fagerberg, R., Finocchi, I., Grandoni, F. & Italiano, G. F. (2007). Optimal Resilient Dynamic Dictionaries. In L. Arge, M. Hoffmann & E. Welzl (Eds.), Algorithms – ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007. Proceedings (pp. 347-358). Springer. https://doi.org/10.1007/978-3-540-75520-3_32

Jørgensen, A. G., Brodal, G. S. & Mølhave, T. (2009). Fault Tolerant External Memory Algorithms. Lecture Notes in Computer Science, 5664, 411-422. https://doi.org/10.1007/978-3-642-03367-4_36

Jørgensen, A. G. & Brodal, G. S. (2009). Data Structures for Range Median Queries. Lecture Notes in Computer Science, 842-851. https://doi.org/10.1007/978-3-642-10631-6_83

Jørgensen, A. G., Brodal, G. S., Mølhave, T. & Moruz, G. (2009). Counting in the Presence of Memory Faults. Lecture Notes in Computer Science, 5878, 842-851. https://doi.org/10.1007/978-3-642-10631-6_85

Jørgensen, A. G., Greve, M., Larsen, K. D. & Truelsen, J. (2010). Cell Probe Lower Bounds and Approximations for Range Mode. Lecture Notes in Computer Science, 6198, 605-616. https://doi.org/10.1007/978-3-642-14165-2_51

Jørgensen, A. G. & Larsen, K. G. (2011). Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2011 (pp. 805-813). Society for Industrial and Applied Mathematics. http://www.siam.org/proceedings/soda/2011/SODA11_062_jorgensena.pdf

Jones, M., Moeslund, J. E., Alexander, C., Bøcher, P. K. & Svenning, J.-C. (2013). Near-ground temperature variability and its predictability in Denmark. Poster session presented at Biodiversitetssymposium 2013, København, Denmark.

Johannsen, V. K., Rojas, S. K., Brunbjerg, A. K., Schumacher, J., Bladt, J., Bladt, J., Nyed, P., Moeslund, J. E., Nord-Larsen, T. & Ejrnæs, R. (2015). Udvikling af et High Nature Value - HNV-skovkort for Danmark: IGN Rapport November 2015, Institut for Geovidenskab og Naturforvaltning, Københavns Universitet, Frederiksberg.

Jiang, S. & Larsen, K. G. (2019). A Faster External Memory Priority Queue with DecreaseKeys. In T. M. Chan (Ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. PRDA19, pp. 1331-1343). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975482.81

Jamalabadi, S., Schwiegelshohn, C. & Schwiegelshohn, U. (2020). Commitment and Slack for Online Load Maximization. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 339–348). Association for Computing Machinery. https://doi.org/10.1145/3350755.3400271

Jafargholi, Z., Larsen, K. G. & Simkin, M. (2021). Optimal oblivious priority queues. In D. Marx (Ed.), ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 (pp. 2366-2383). Association for Computing Machinery.

Jacob, R., Larsen, K. G. & Nielsen, J. B. (2019). Lower Bounds for Oblivious Data Structures. In T. M. Chan (Ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2439-2447). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975482.149

Høye, T. T., Olsen, K., Moeslund, J. E., Strandberg, M. T. & Kjær, C., (2019). Oversigt og status for de danske sommerfuglearter, 8 p., Notat fra DCE - Nationalt Center for Miljø og Energi (2011-2019) https://dce.au.dk/fileadmin/dce.au.dk/Udgivelser/Notater_2019/Status_danske_sommerfugle.pdf

Holt, M. K., Johansen, J. & Brodal, G. S. (2014). On the Scalability of Computing Triplet and Quartet Distances. In C. C. McGeoch & U. Meyer (Eds.), 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 9-19). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973198.2

Høgsgaard, M. M., Larsen, K. G. & Ritzert, M. (2023). AdaBoost is not an Optimal Weak to Strong Learner. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato & J. Scarlett (Eds.), Proceedings of ICML 2023 (Vol. 202, pp. 13118-13140). MLResearch Press.

Høgsgaard, M. M., Larsen, K. G. & Mathiasen, M. E. (2024). The Many Faces of Optimal Weak-to-Strong Learning. https://arxiv.org/pdf/2408.17148

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

Høgsgaard, M. M., Kamma, L., Larsen, K. G., Nelson, J. & Schwiegelshohn, C. (2024). Sparse Dimensionality Reduction Revisited. In International Conference on Machine Learning (pp. 18454-18469). 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.

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

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)

Haxen, M., Raeburn, M., Afshani, P. & Karras, P. (2021). Centerpoint Query Authentication. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21) (pp. 3083-3087). Association for Computing Machinery. https://doi.org/10.1145/3459637.3482072

Displaying results 101 to 150 out of 454

Revised 01.09.2025

Publications

Head of research