Aarhus University Seal

Publications

Contribution to book anthology

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. & 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
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
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. (2025). Efficient Optimal PAC Learning. In Proceedings of The 36th International Conference on Algorithmic Learning Theory (pp. 578-580). PMLR.
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. & 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
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
Grønlund, A., Kamma, L., Larsen, K. G., Mathiasen, A. & Nelson, J. (2019). Margin-Based Generalization Lower Bounds for Boosted Classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox & R. Garnett (Eds.), Advances in Neural Information Processing Systems 32 (NIPS 2019) (Vol. 32). Neural Information Processing Systems Foundation. https://arxiv.org/abs/1909.12518
Grønlund, A., Kamma, L. & Larsen, K. G. (2020). Margins are Insufficient for Explaining Gradient Boosting. In H. Larochelle, MA. Ranzato, R. Hadsell, M.-F. Balcan & H.-T. Lin (Eds.), Advances in Neural Information Processing Systems 33 (NeurIPS 2020) (Vol. 2020-December) https://proceedings.neurips.cc/paper/2020/hash/146f7dd4c91bc9d80cf4458ad6d6cd1b-Abstract.html
Grønlund, A., Kamma, L. & Larsen, K. G. (2020). Near-Tight Margin-Based Generalization Bounds for Support Vector Machines. In H. Daumé III & A. Singh (Eds.), International Conference on Machine Learning (pp. 3737-3746). MLResearch Press. http://proceedings.mlr.press/v119/gronlund20a.html
Grønlund, A., Larsen, K. G. & Mathiasen, A. (2019). Optimal Minimal Margin Maximization with Boosting. In K. Chaudhuri & R. Salakhutdinov (Eds.), 36th International Conference on Machine Learning, ICML 2019 (Vol. 97, pp. 7734-7743). International Machine Learning Society (IMLS). http://proceedings.mlr.press/v97/mathiasen19a/mathiasen19a.pdf
Green Larsen, K., Mitzenmacher, M. & Tsourakakis, C. (2020). Clustering with a faulty oracle. In Y. Huang, I. King, T.-Y. Liu & M. van Steen (Eds.), WWW '20: Proceedings of The Web Conference 2020 (pp. 2831-2834). Association for Computing Machinery. https://doi.org/10.1145/3366423.3380045
Grandoni, F., Schwiegelshohn, C., Solomon, S. & Uzrad, A. (2022). Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds. In Symposium on Simplicity in Algorithms (SOSA) (pp. 12-23). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611977066.2
Goswami, M., Jørgensen, A. G., Larsen, K. G. & Pagh, R. (2015). Approximate Range Emptiness in Constant Time and Optimal Space. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15 (pp. 769-775). Society for Industrial and Applied Mathematics. http://dl.acm.org/citation.cfm?id=2133036&picked=prox
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)
Freksen, C. B. & Larsen, K. G. (2017). On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. In O. Yoshio & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) (pp. 32:1-32:12). Article 32 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2017.32
Fleischhacker, N., Larsen, K. G. & Simkin, M. (2023). How to Compress Encrypted Data. In C. Hazay & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I (pp. 551-577). Springer. https://doi.org/10.1007/978-3-031-30545-0_19
Fleischhacker, N., Larsen, K. G., Obremski, M. & Simkin, M. (2024). Invertible Bloom Lookup Tables with Less Memory and Randomness. In T. Chan, J. Fischer, J. Iacono & G. Herman (Eds.), 32nd Annual European Symposium on Algorithms, ESA 2024 Article 54 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2024.54
Fleischhacker, N., Larsen, K. G. & Simkin, M. (2022). Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions. In O. Dunkelman & S. Dziembowski (Eds.), Advances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings (pp. 764-781). Springer. https://doi.org/10.1007/978-3-031-07085-3_26
Farhadi, A., Hajiaghayi, M. T., Larsen, K. G. & Shi, E. (2019). Lower bounds for external memory integer sorting via network coding. In M. Charikar & E. Cohen (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 997-1008). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316337
Fandina, O. N., Høgsgaard, M. M. & Larsen, K. G. (2023). Barriers for Faster Dimensionality Reduction. In P. Berenbrink, P. Bouyer, A. Dawar & M. M. Kante (Eds.), 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 Article 31 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2023.31
Fandina, O. N., Høgsgaard, M. M. & Larsen, K. G. (2023). The Fast Johnson-Lindenstrauss Transform Is Even Faster. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato & J. Scarlett (Eds.), Proceedings of ICML 2023 (Vol. 202, pp. 9689-9715). MLResearch Press.
Eenberg, K., Larsen, K. G. & Yu, H. (2017). DecreaseKeys are expensive for external memory priority queues. In STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Vol. Part F128415, pp. 1081-1093). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055437
de Berg, M., Tsirogiannis, C. & Wilkinson, B. T. (2015). Fast computation of categorical richness on raster data sets and related problems. In GIS '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems Article 18 https://doi.org/10.1145/2820783.2820825
de Berg, M., Tsirogiannis, C. & Wilkinson, B. (2015). Fast Computation of Categorical Richness on Raster Data Sets and Related Problems. In Proceedings. Workshop on Massive Data Algorithmics (MASSIVE) (pp. 86-107)
Damgård, I. B., Larsen, K. G. & Yakoubov, S. (2021). Broadcast secret-sharing, bounds and applications. In S. Tessaro (Ed.), 2nd Conference on Information-Theoretic Cryptography, ITC 2021 Article 10 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITC.2021.10
Damgård, I., Larsen, K. G. & Nielsen, J. B. (2019). Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. In A. Boldyreva & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings (Vol. II, pp. 61-84). Springer. https://doi.org/10.1007/978-3-030-26951-7_3
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.
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
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., Saulpic, D. & Schwiegelshohn, C. (2021). A new coreset framework for clustering. In S. Khuller & V. V. Williams (Eds.), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 169-182). Association for Computing Machinery. https://doi.org/10.1145/3406325.3451022
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.
Cohen-Addad, V., Saulpic, D. & Schwiegelshohn, C. (2023). Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1105-1130). IEEE. https://doi.org/10.1109/FOCS57990.2023.00066
Cohen-Addad, V., Saulpic, D. & Schwiegelshohn, C. (2021). Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021 (pp. 21085-21098). Neural Information Processing Systems Foundation.
Cohen-Addad, V., Larsen, K. G., Saulpic, D., Schwiegelshohn, C. & Sheikh-Omar, O. A. (2022). Improved Coresets for Euclidean k-Means. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho & A. Oh (Eds.), Advances in Neural Information Processing Systems 35 - 36th Conference on Neural Information Processing Systems, NeurIPS 2022 Neural Information Processing Systems Foundation.
Cohen-Addad, V., Epasto, A., Lattanzi, S., Mirrokni, V., Munoz Medina, A., Saulpic, D., Schwiegelshohn, C. & Vassilvitskii, S. (2022). Scalable Differentially Private Clustering via Hierarchically Separated Trees. In KDD 2022 - Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 221-230). Association for Computing Machinery. https://doi.org/10.1145/3534678.3539409
Cohen-Addad, V., Larsen, K. G., Saulpic, D. & Schwiegelshohn, C. (2022). Towards optimal lower bounds for k-median and k-means coresets. In S. Leonardi & A. Gupta (Eds.), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1038-1051). Association for Computing Machinery. https://doi.org/10.1145/3519935.3519946
Clifford, R., Jørgensen, A. G. & Larsen, K. G. (2015). New Unconditional Hardness Results for Dynamic and Online Problems. In 56th IEEE Symposium on Foundations of Computer Science (FOCS) Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS IEEE Computer Society Press. http://arxiv.org/pdf/1504.01836v1.pdf
Clifford, R., Grønlund, A., Larsen, K. G. & Starikovskaya, T. (2018). Upper and lower bounds for dynamic data structures on strings. In R. Niedermeier & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018 (Vol. 96, pp. 22:1-22:14). Article 22 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2018.22
Chung, E. & Larsen, K. G. (2023). Stronger 3SUM-Indexing Lower Bounds. In N. Bansal & V. Nagarajan (Eds.), Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 444-455). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch19
Cheng, P. & Afshani, P. (2023). An Optimal Lower Bound for Simplex Range Reporting. In T. Kavitha & K. Mehlhorn (Eds.), 6th Symposium on Simplicity in Algorithms (SOSA 2023) (pp. 272-277). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977585.ch25
Chan, T. M. & Wilkinson, B. T. (2013). Adaptive and Approximate Orthogonal Range Counting. In S. Khanna (Ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 (pp. 241-251). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973105.18