Publications

Son, W. & Afshani, P. (2015). Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls. In R. Jain, S. Jain & F. Stephan (Eds.), Theory and Applications of Models of Computation: 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings (pp. 189-199 ). Springer VS. https://doi.org/10.1007/978-3-319-17142-5

Wilkinson, B. T. (2015). Exploring the Problem Space of Orthogonal Range Searching. Department of Computer Science, Aarhus University.

Wilkinson, B. T. (2015). Revisiting visibility in the plane. Paper presented at International Symposium on Computational Geometry, Eindhoven, Netherlands. http://www.madalgo.au.dk/~bw/papers/2015W.pdf

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). Article 93 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. https://doi.org/10.4230/LIPIcs.ICALP.2016.93

Baum, C., Damgård, I. B., Larsen, K. G. & Nielsen, M. (2016). How to prove knowledge of small secrets. In J. Katz & M. Robshaw (Eds.), Advances in Cryptology - 36th Annual International Cryptology Conference, CRYPTO 2016, Proceedings: CRYPTO 2016: Advances in Cryptology – CRYPTO 2016 (Vol. 9816, pp. 478-498). Springer VS. https://doi.org/10.1007/978-3-662-53015-3_17

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

Bladt, J., Brunbjerg, A. K., Moeslund, J. E., Petersen, A. H. & Ejrnæs, R. (2016). Opdatering af lokal bioscore for biodiversitetskortet for Danmark 2015. In DCE rapport http://dce2.au.dk/pub/TR74.pdf

Brodal, G. S. (2016). External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates. In N. Ollinger & H. Vollmer (Eds.), 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Vol. 47, pp. 23:1-23:14). Article 23 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. https://doi.org/10.4230/LIPIcs.STACS.2016.23

Brunbjerg, A. K., Bladt, J., Brink, M., Fredshavn, J. R., Mikkelsen, P., Moeslund, J. E., Nygaard, B., Skov, F. & Ejrnæs, R. (2016). Development and implementation of a High Nature Value (HNV) farming indicator for Denmark. Ecological Indicators, 61(2), 274-281. Advance online publication. https://doi.org/10.1016/j.ecolind.2015.09.027

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

Grønlund, A. & Larsen, K. G. (2016). Towards Tight Lower Bounds for Range Reporting on the RAM. Leibniz International Proceedings in Informatics, 55, 92:1 - 92:12. https://doi.org/10.4230/LIPIcs.ICALP.2016.92

Larsen, K. G., Nelson, J., Nguyen, H. L. & Thorup, M. (2016). Heavy hitters via cluster-preserving clustering. In Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 (pp. 61-70). Article 7782918 IEEE. https://doi.org/10.1109/FOCS.2016.16

Larsen, K. G. & Nelson, J. (2016). The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. Leibniz International Proceedings in Informatics, 55, 82:1 - 82:11. https://doi.org/10.4230/LIPIcs.ICALP.2016.82

Moeslund, J. E. (2016, Jul 15). Small steps for man, giant leaps for plants. http://blogs.springer.com/lst/small-steps-man-giant-leaps-plants/

Stølting Brodal, G., Davoodi, P., Lewenstein, M., Raman, R. & Satti, S. R. (2016). Two dimensional range minimum queries and Fibonacci lattices. Theoretical Computer Science, 638, 33-43. https://doi.org/10.1016/j.tcs.2016.02.016

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. https://doi.org/10.4230/LIPIcs.SoCG.2016.63

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

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.

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). Article 2 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. https://doi.org/10.4230/LIPIcs.ESA.2017.2

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

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. https://doi.org/10.4230/LIPIcs.ISAAC.2017.12

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

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). Article 21 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2017.21

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

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

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 Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ISAAC.2017.32

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

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

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

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

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

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, Article 2.3. https://doi.org/10.1145/3209685

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

Bury, M., Schwiegelshohn, C. & Sorella, M. (2018). Sketch 'em all: Fast approximate similarity search for dynamic data streams. WSDM 2018 - Proceedings of the 11th ACM International Conference on Web Search and Data Mining, 72-80. https://doi.org/10.1145/3159652.3159694

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. 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). Article 22 Schloss Dagstuhl--Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2018.22

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.

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

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.

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

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. https://doi.org/10.1145/3188745.3188790

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. https://doi.org/10.1007/978-3-319-96881-0_18

Munteanu, A. & Schwiegelshohn, C. (2018). Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms. KI - Kunstliche Intelligenz, 32(1), 37-53. https://doi.org/10.1007/s13218-017-0519-3

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

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 Article 3 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2019.3

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 Article 2 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2019.2

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 Article 4 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2019.4

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, Article 10. https://doi.org/10.4230/LIPIcs.ICALP.2019.10

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

Displaying results 201 to 250 out of 343