Publications

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://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.81

Afshani, P. (2019). A new lower bound for semigroup orthogonal range searching. In G. Barequet & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [3] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 129 https://doi.org/10.4230/LIPIcs.SoCG.2019.3

Sporbert, M., Bruelheide, H., Seidler, G., Keil, P., Jandt, U., Austrheim, G., Biurrun, I., Campos, J. A., Čarni, A., Chytrý, M., Csiky, J., De Bie, E., Dengler, J., Golub, V., Grytnes, J-A., Indreica, A., Jansen, F., Martin Jiroušek, M., Lenoir, J. ... Welk, E. (2019). Assessing sampling coverage of species distribution in biodiversity databases. Journal of Vegetation Science, 30(4), 620-632. https://doi.org/10.1111/jvs.12763

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. Lecture Notes in Computer Science Vol. 11693 https://doi.org/10.1007/978-3-030-26951-7_3

Larsen, K. G. (2019). Constructive Discrepancy Minimization with Hereditary L2 Guarantees. In R. Niedermeier & C. Paul (Eds.), 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) [48] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics Vol. 126 https://doi.org/10.4230/LIPIcs.STACS.2019.48

Afshani, P., Fagerberg, R., Hammer, D., Jacob, R., Kostitsyna, I., Meyer, U., Penschuck, M. & Sitchinava, N. (2019). Fragile complexity of comparison-based algorithms. In M. A. Bender, O. Svensson & G. Herman (Eds.), 27th Annual European Symposium on Algorithms, ESA 2019 [2] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 144 https://doi.org/10.4230/LIPIcs.ESA.2019.2

Larsen, K. G., Nelson, J., Huy L Nguyen & Thorup, M. (2019). Heavy Hitters via Cluster-Preserving Clustering. Communications of the ACM, 62(8), 95-100. https://doi.org/10.1145/3339185

Afshani, P. & Phillips, J. M. (2019). Independent range sampling, revisited again. In G. Barequet & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [4] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 129 https://doi.org/10.4230/LIPIcs.SoCG.2019.4

Moeslund, J. E., Zlinszky, A., Ejrnæs, R., Brunbjerg, A. K., Bøcher, P. K., Svenning, J. C. & Normand, S. (2019). Light detection and ranging explains diversity of plants, fungi, lichens, and bryophytes across multiple habitats and large geographic extent. Ecological Applications, 29(5), [e01907]. https://doi.org/10.1002/eap.1907

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. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms Vol. PRDA19 https://doi.org/10.1137/1.9781611975482.149

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. A C M Symposium on the Theory of Computing. Annual Proceedings https://doi.org/10.1145/3313276.3316337

Afshani, P., Freksen, C. B., Kamma, L. & Larsen, K. G. (2019). Lower bounds for multiplication via network coding. Leibniz International Proceedings in Informatics, LIPIcs, 132, [10]. https://doi.org/10.4230/LIPIcs.ICALP.2019.10

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) Neural Information Processing Systems Foundation. https://arxiv.org/abs/1909.12518

Grønlund, A., Larsen, K. G. & Mathiasen, A. (2019). Optimal Minimal Margin Maximization with Boosting. In K. Chaudhuri & R. Salakhutdinov (Eds.), Proceedings of th 36th International Conference on Machine Learning (Vol. 97, pp. 4392-4401). International Machine Learning Society (IMLS). Proceedings of Machine Learning Research Vol. 97 http://proceedings.mlr.press/v97/mathiasen19a/mathiasen19a.pdf

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 https://dce.au.dk/fileadmin/dce.au.dk/Udgivelser/Notater_2019/Status_danske_sommerfugle.pdf

Fløjgaard, C., Frøslev, T. G., Brunbjerg, A. K., Bruun, H. H., Moeslund, J. E., Hansen, A. J. & Ejrnæs, R. (2019). Predicting provenance of forensic soil samples: Linking soil to ecological habitats by metabarcoding and supervised classification. PLOS ONE, 14(7), [e0202844]. https://doi.org/10.1371/journal.pone.0202844

Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K. G. & Mehlhorn, K. (2019). The query complexity of a permutation-based variant of Mastermind. Discrete Applied Mathematics, 260, 28-50. https://doi.org/10.1016/j.dam.2019.01.007

Bruelheide, H., Dengler, J., Jiménez-Alfaro, B., Purschke, O., Hennekens, S. M., Chytrý, M., Pillar, V. D., Jansen, F., Kattge, J., Sandel, B., Aubin, I., Biurrun, I., Field, R., Haider, S., Jandt, U., Lenoir, J., Peet, R. K., Peyre, G., Sabatini, F. M. ... Zverev, A. (2019). sPlot – A new tool for global vegetation analyses. Journal of Vegetation Science, 30(2), 161-186. https://doi.org/10.1111/jvs.12710

Afshani, P., De Berg, M., Casanova, H., Karsin, B., Lambrechts, C., Sitchinava, N. & Tsirogiannis, C. (2018). An efficient algorithm for the 1D total visibility-index problem and its parallelization. ACM Journal of Experimental Algorithmics, 23, [2.3]. https://doi.org/10.1145/3209685

Larsen, K. G., Weinstein, O. & Yu, H. (2018). Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. In M. Henzinger, D. Kempe & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 978-989). Association for Computing Machinery. A C M. S I G A C T - S I G M O D - S I G A R T Symposium on Principles of Database Systems. Proceedings No. 2018 https://doi.org/10.1145/3188745.3188790

Groom, G. B., Bladt, J., Moeslund, J. E. & Ejrnæs, R. (2018). Developing biodiversity proxies: Technical description. Aarhus Universitet, DCE – Nationalt Center for Miljø og Energi ©. Technical Report from DCE – Danish Centre for Environment and Energy No. 123

Freksen, C. B., Kamma, L. & Larsen, K. G. (2018). Fully Understanding the Hashing Trick. arXiv.org. http://arxiv.org/abs/1805.08539

Freksen, C. B., Kamma, L. & Larsen, K. G. (2018). Fully Understanding the Hashing Trick. 1. Poster session presented at Neural Information Processing Systems Conference, Montreal, Canada.

Dalsgaard, P., Pedersen, B. P., Dimke, H., Møller, N. M., Normand, S., Bjørk, R., Bille, M. & Larsen, K. G. (2018). Opholdskrav i skatteaftale hæmmer dansk forskning. Politiken, (Sektion 2 (Kultur)), 7.

Tsourakakis, C. E., Mitzenmacher, M., Larsen, K. G., Blasiok, J., Lawson, B., Nakkiran, P. & Nakos, V. (2018). Predicting Positive and Negative Links with Noisy Queries: Theory Practice. arXiv.org. http://arxiv.org/abs/1709.07308

Chakraborty, D., Kamma, L. & Larsen, K. G. (2018). Tight cell probe bounds for succinct boolean matrix-Vector multiplication. In STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1297-1306). Association for Computing Machinery. A C M Symposium on the Theory of Computing. Annual Proceedings No. 2018 https://doi.org/10.1145/3188745.3188830

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). [22] Schloss Dagstuhl--Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics No. 96 https://doi.org/10.4230/LIPIcs.STACS.2018.22

Ejrnæs, R., Moeslund, J. E., Brunbjerg, A. K., Groom, G. B. & Bladt, J. (2018). Videreudvikling af lokal bioscore for biodiversitetskortet for Danmark. Aarhus Universitet, DCE – Nationalt Center for Miljø og Energi ©. Teknisk rapport fra DCE - Nationalt Center for Miljø og Energi Vol. 122 http://dce2.au.dk/pub/TR122.pdf

Larsen, K. G. & Nielsen, J. B. (2018). Yes, There is an Oblivious RAM Lower Bound! In H. Shacham & A. Boldyreva (Eds.), Advances in Cryptology -- CRYPTO 2018 (pp. 523-542). Springer VS. Lecture Notes in Computer Science (LNCS) No. 10992 https://doi.org/10.1007/978-3-319-96881-0_18

Bringmann, K., Grønlund, A. & Larsen, K. G. (2017). A Dichotomy for Regular Expression Membership Testing. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 307-318). IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2017.36

Berglin, E. & Brodal, G. S. (2017). A simple greedy algorithm for dynamic graph orientation. In Y. Okamoto & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) (pp. 12:1-12:12). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics No. 92 https://doi.org/10.4230/LIPIcs.ISAAC.2017.12

Afshani, P., De Berg, M., Casanova, H., Karsin, B., Lambrechts, C., Sitchinava, N. & Tsirogiannis, C. (2017). An efficient algorithm for the 1D total visibility-index problem. In S. Fekete & V. Ramachandran (Eds.), 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Vol. PRAL17, pp. 218-231). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974768.18

Brodal, G. S. & Mampentzidis, K. (2017). Cache oblivious algorithms for computing the triplet distance between trees. In K. Pruhs & C. Sohler (Eds.), 25th European Symposium on Algorithms, ESA 2017 (Vol. 87, pp. 21:1--21:14). [21] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics Vol. 87 https://doi.org/10.4230/LIPIcs.ESA.2017.21

Afshani, P., Bender, M. A., Farach-Colton, M., Fineman, J. T., Goswami, M. & Tsai, M. T. (2017). Cross-Referenced dictionaries and the limits of write optimization. In P. N. Klein (Ed.), 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1523-1532). Association for Computing Machinery.

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

Brunbjerg, A. K., Bruun, H. H., Moeslund, J. E., Sadler, J. P., Svenning, J-C. & Ejrnæs, R. (2017). Ecospace: a unified framework for understanding variation in terrestrial biodiversity. Basic and Applied Ecology, 18, 86-94. https://doi.org/10.1016/j.baae.2016.09.002

Larsen, K. G. & Williams, R. (2017). Faster Online Matrix-Vector Multiplication. In P. N. Klein (Ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. PRDA17, pp. 2182-2189). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782

Peterka, T., Hájek, M., Jiroušek, M., Jiménez-Alfaro, B., Aunina, L., Bergamini, A., Dítě, D., Felbaba-Klushyna, L., Graf, U., Hájková, P., Hettenbergerová, E., Ivchenko, T. G., Jansen, F., Koroleva, N. E., Lapshina, E. D., Lazarević, P. M., Moen, A., Napreenko, M. G., Pawlikowski, P. ... Chytrý, M. (2017). Formalized classification of European fen vegetation at the alliance level. Applied Vegetation Science, 20(1), 124-142. https://doi.org/10.1111/avsc.12271

Alamdari, S., Angelini, P., Barrera-Cruz, F., Chan, T. M., Da Lozzo, G., Di Battista, G., Frati, F., Haxell, P., Lubiw, A., Patrignani, M., Roselli, V., Singla, S. & Wilkinson, B. T. (2017). How to Morph Planar Graph Drawings. S I A M Journal on Computing, 46(2), 824-852. https://doi.org/10.1137/16M1069171

Madalgo, P. A., Barbay, J. & Chan, T. M. (2017). Instance-optimal geometric algorithms. Journal of the ACM, 64(1), [3]. https://doi.org/10.1145/3046673

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). [32] Schloss Dagstuhl--Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics Vol. 92 https://doi.org/10.4230/LIPIcs.ISAAC.2017.32

Afshani, P. & Tsakalidis, K. (2018). Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges. Algorithmica, 80(11), 3192-3206. https://doi.org/10.1007/s00453-017-0376-3

Larsen, K. G. & Nelson, J. (2017). Optimality of the Johnson-Lindenstrauss Lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 633-638). [8104096] https://doi.org/10.1109/FOCS.2017.64

Afshani, P. & Van Duijn, I. (2017). Permuting and batched geometric lower bounds in the I/O model. In K. Pruhs & C. Sohler (Eds.), 25th European Symposium on Algorithms, ESA 2017 (Vol. 87, pp. 2:1-2:13). [2] Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics Vol. 87 https://doi.org/10.4230/LIPIcs.ESA.2017.2

Moeslund, J. E., Brunbjerg, A. K., Clausen, K., Dalby, L., Fløjgaard, C., Juel, A. & Lenoir, J. (2017). Using dark diversity and plant characteristics to guide conservation and restoration. Journal of Applied Ecology, 54(6), 1730-1741. https://doi.org/10.1111/1365-2664.12867

Chan, T. M. & Wilkinson, B. T. (2016). Adaptive and approximate orthogonal range counting. ACM Transactions on Algorithms, 12(4), 45:1-45:15. [45]. https://doi.org/10.1145/2830567

Bladt, J., Brunbjerg, A. K., Moeslund, J. E., Petersen, A. H. & Ejrnæs, R., (2016). Appendix 6: Opdatering af biodiversitetskortet for Danmark 2015, 10 p., Notat fra DCE - Nationalt Center for Miljø og Energi

Yon, J., Won, S. B., Cheng, S. W., Cheong, O. & Wilkinson, B. T. (2016). Approximating convex shapes with respect to symmetric difference under homotheties. In S. Fekete & A. Lubiw (Eds.), 32nd International Symposium on Computational Geometry, SoCG 2016 (Vol. 51, pp. 63.1-63.15). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics Vol. 51 https://doi.org/10.4230/LIPIcs.SoCG.2016.63

Afshani, P. & Nielsen, J. A. S. (2016). Data Structure Lower Bounds for Document Indexing Problems. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Vol. 55, pp. 93:1-93:15). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics Vol. 55 https://doi.org/10.4230/LIPIcs.ICALP.2016.93