Department of Computer Science

Aarhus University Seal
 Department of Computer Science Research Publications

Publications

Sort by: Type and year

2023

Contribution to book anthology

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
Afshani, P., Cheng, P., Basu Roy, A. & Wei, Z. (2023). On Range Summary Queries. In K. Etessami, U. Feige & G. Puppis (Eds.), 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (pp. 7:1-7:17). Article 7 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2023.7
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
Afshani, P. & Cheng, P. (2023). Lower Bounds for Intersection Reporting Among Flat Objects. In E. W. Chambers & J. Gudmundsson (Eds.), 39th International Symposium on Computational Geometry, SoCG 2023 Article 3 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2023.3
Brodal, G. S., Rysgaard, C. M. & Svenning, R. (2023). External Memory Fully Persistent Search Trees. In B. Saha & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1410-1423). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585140
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
Brodal, G. S. & Wild, S. (2023). Funnelselect: Cache-Oblivious Multiple Selection. In I. Li Gortz, M. Farach-Colton, S. J. Puglisi & G. Herman (Eds.), 31st Annual European Symposium on Algorithms, ESA 2023 (pp. 25:1-25:17). Article 25 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2023.25
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.
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
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.
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.
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
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
Viallat, V. C. A., Grandoni, F., Lee, E. & Schwiegelshohn, C. (2023). Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. In Thirty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) (Vol. 1, pp. 940-986). Association for Computing Machinery.
Schwiegelshohn, C. (2023). Fitting Data on a Grain of Rice. In I. Chatzigiannakis & I. Karydis (Eds.), Algorithmic Aspects of Cloud Computing: 8th International Symposium, ALGOCLOUD 2023, Amsterdam, The Netherlands, September 5, 2023, Revised Selected Papers (pp. 1-8). Springer. https://doi.org/10.1007/978-3-031-49361-4_13
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
Brodal, G. S., Rysgaard, C. M., Schou, J. K. R. & Svenning, R. (2023). Space-Efficient Functional Offline-Partially-Persistent Trees with Applications to Planar Point Location. In P. Morin & S. Suri (Eds.), Algorithms and Data Structures: 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings (pp. 644-659). Springer. https://doi.org/10.1007/978-3-031-38906-1_43
Larsen, K. G. & Yu, H. (2023). Super-Logarithmic Lower Bounds for Dynamic Graph Problems. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1589-1604). IEEE. https://doi.org/10.1109/FOCS57990.2023.00096
Bucarelli, M. S., Larsen, M. F., Schwiegelshohn, C. & Toftrup, M. B. (2023). On Generalization Bounds for Projective Clustering. In Advances in Neural Information Processing Systems https://papers.nips.cc/paper_files/paper/2023/hash/e30bf4765ae6b16a87fb4d7b0b3b3dec-Abstract-Conference.html
Mai, T., Munteanu, A., Musco, C., Rao, A. B., Schwiegelshohn, C. & Woodruff, D. P. (2023). Optimal Sketching Bounds for Sparse Linear Regression. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (pp. 11288-11316). PMLR. https://proceedings.mlr.press/v206/mai23a.html
Brodal, G. S. (2022). Priority Queues with Decreasing Keys. In P. Fraigniaud & Y. Uno (Eds.), 11th International Conference on Fun with Algorithms, FUN 2022 (pp. 8:1-8:19). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FUN.2022.8
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
Bartal, Y., Fandina, O. N. & Larsen, K. G. (2022). Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry, SoCG 2022 Article 13 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2022.13
Afshani, P., de Berg, M., Buchin, K., Gao, J., Löffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H. & Yang, H. T. (2022). On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry, SoCG 2022 Article 2 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2022.2
Afshani, P. & Cheng, P. (2022). On Semialgebraic Range Reporting. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry, SoCG 2022 Article 3 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2022.3
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
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
Afshani, P., Killmann, R. & Larsen, K. G. (2022). Hierarchical Categories in Colored Searching. In S. W. Bae & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation, ISAAC 2022 Article 25 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2022.25
Braverman, V., Cohen-Addad, V., Jiang, S. H.-C., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M. B. & Wu, X. (2022). The Power of Uniform Sampling for Coresets. In Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022 (pp. 462-473). IEEE. https://doi.org/10.1109/FOCS54457.2022.00051
Afshani, P., Iacono, J., Jayapaul, V., Karsin, B. & Sitchinava , N. (2022). Locality-of-Reference Optimality of Cache-Oblivious Algorithms. In 3rd Symposium on Algorithmic Principles of Computer Systems, (APOCS) (pp. 31 - 45). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977059.3
Schwiegelshohn, C. & Sheikh-Omar, O. A. (2022). An Empirical Evaluation of k-Means Coresets. In S. Chechik, G. Navarro, E. Rotenberg & G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022 (pp. 84:1-84:17). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2022.84
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.
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
Afshani, P. (2021). A Lower Bound for Dynamic Fractional Cascading. In ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 (pp. 2229-2248). Association for Computing Machinery. https://doi.org/10.5555/3458064.3458197
Afshani, P., de Berg, M., Buchin, K., Gao, J., Loffler, M., Nayyeri, A., Raichel, B., Sarkar, R., Wang, H. & Wang, H.-T. (2021). Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency. In S. M. LaValle, M. Lin, T. Ojala, D. Shell & J. Yu (Eds.), Algorithmic Foundations of Robotics XIV-Part A: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics (pp. 107-123). Springer. https://doi.org/10.1007/978-3-030-66723-8_7
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
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
Brodal, G. S., Fagerberg, R., Hammer, D., Meyer, U., Penschuck, M. & Tran, H. (2021). An experimental study of external memory algorithms for connected components. In D. Coudert & E. Natale (Eds.), 19th International Symposium on Experimental Algorithms, SEA 2021 (pp. 23). Article 23 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SEA.2021.23
Afshani, P. & Cheng, P. (2021). Lower bounds for semialgebraic range searching and stabbing problems. In K. Buchin & E. C. de Verdiere (Eds.), 37th International Symposium on Computational Geometry, SoCG 2021 Article 8 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2021.8
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
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.
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
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.
Larsen, K. G., Malkin, T., Weinstein, O. & Yeo, K. (2020). Lower Bounds for Oblivious Near-Neighbor Search. In S. Chawla (Ed.), SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1116-1134). Society for Industrial and Applied Mathematics. https://doi.org/10.5555/3381089.3381157
Zardbani, F., Afshani, P. & Karras, P. (2020). Revisiting the theory and practice of database cracking. In A. Bonifati, Y. Zhou, M. A. Vaz Salles, A. Bohm, D. Olteanu, G. Fletcher, A. Khan & B. Yang (Eds.), Advances in Database Technology - EDBT 2020: 23rd International Conference on Extending Database Technology, Proceedings (pp. 415-418). openproceedings.org. https://doi.org/10.5441/002/edbt.2020.46
Afshani, P., van Duijn, I., Killmann, R. & Nielsen, J. S. (2020). A lower bound for jumbled indexing. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (pp. 592-606). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975994.36
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
Larsen, K. G., Mitzenmacher, M. & Tsourakakis, C. E. (2020). Optimal Learning of Joint Alignments with a Faulty Oracle. In 2020 IEEE International Symposium on Information Theory, ISIT 2020 (pp. 2492-2497). IEEE. https://doi.org/10.1109/ISIT44484.2020.9174310
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
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

Displaying results 101 to 150 out of 451

Previous

1

2

3

4

5

6

7

8

9

10

Next

Head of research

Revised 01.09.2025