Publications

Afshani, P. & Cheng, P. (2020). 2D generalization of fractional cascading on axis-aligned planar subdivisions. In Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020 (pp. 716-727). Article 9317953 IEEE Computer Society Press. https://doi.org/10.1109/FOCS46700.2020.00072

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

Brodal, G. S., Kejlberg-Rasmussen, C. & Truelsen, J. (2010). A Cache-Oblivious Implicit Dictionary with the Working Set Property. Lecture Notes in Computer Science, 6507, 37-48. https://doi.org/10.1007/978-3-642-17514-5_4

Afshani, P. & Sitchinava , N. (2025). A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM. In ACACM-SIAM Symposium on Discrete Algorithms, SODA 2025 (pp. 3998-4008). Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.136

Brodal, G. S. & Husfeldt, T. (1996). A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. Department of Computer Science, Aarhus University. BRICS Report Series No. 96-1 http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf

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.

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

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

Brody, J. E. & Larsen, K. G. (2015). Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures. Theory of Computing, 11(19), 471-489. https://doi.org/10.4086/toc.2015.v011a019

Leblanc, C., Bonnet, P., Servajean, M., Chytrý, M., Aćić, S., Argagnon, O., Bergamini, A., Biurrun, I., Bonari, G., Campos, J. A., Čarni, A., Ćušterevska, R., De Sanctis, M., Dengler, J., Garbolino, E., Golub, V., Jandt, U., Jansen, F., Lebedeva, M. ... Joly, A. (2024). A deep-learning framework for enhancing habitat identification based on species composition. Applied Vegetation Science, 27(3), Article e12802. https://doi.org/10.1111/avsc.12802

Sølvsten, S., van de Pol, J., Jakobsen, A. B., Rysgaard, C. M., Carstensen, E. F. & Thomasen, M. W. B. (2021). Adiar: An I/O-efficient implementation of Decision Diagrams. Software, GitHub. https://doi.org/10.5281/zenodo.4718218

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

Hájek, M., Jimenez-Alfaro, B., Hájek, O., Brancaleoni, L., Cantonati, M., Carbognani, M., Dedić, A., Dítě, D., Gerdol, R., Hájková, P., Horsáková, V., Jansen, F., Kamberović, J., Kapfer, J., Kolari, T. H. M., Lamentowicz, M., Lazarević, P. M., Mašić, E., Moeslund, J. E. ... Biţă-Nicolae, C. (2021). A European map of groundwater pH and calcium. Earth System Science Data, 13(3), 1089-1105. https://doi.org/10.5194/essd-13-1089-2021

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

Afshani, P., Hamilton, C. & Zeh, N. (2009). A general approach for cache-oblivious range reporting and approximate range counting. In Proceedings of the 25th annual symposium on Computational geometry Association for Computing Machinery. https://doi.org/10.1145/1542362.1542413

Afshani, P., Hamilton, C. & Zeh, N. (2010). A general approach for cache-oblivious range reporting and approximate range counting. Computational Geometry, 43(8), 700-712. https://doi.org/10.1016/j.comgeo.2010.04.003

Alexander, C., Moeslund, J. E., Bøcher, P. K., Arge, L. & Svenning, J.-C. (2013). Airborne laser scanner (LiDAR) proxies for understory light conditions. Remote Sensing of Environment, 134, 152-161. https://doi.org/10.1016/j.rse.2013.02.028

Rysgaard, C. M. (2025). A Journey through Persistence, External Memory, Trees, and other Unrelated Problems. [PhD dissertation, Aarhus University].

Brodal, G. S., Frigioni, D. & Marchetti-Spaccamela, A. (Eds.) (2001). Algorithm Engineering: Proceedings of 5th International Workshop on Algorithm Engineering (WAE 2001). (2141 i Lecture Notes in Computer Science ed.) Springer.

Schou, J. K. R. (2025). Algorithmic Innovation through Persistence, Topology, and Geometry. [PhD dissertation, Aarhus University].

Sand, A., Holt, M. K., Johansen, J., Fagerberg, R., Pedersen, C. N. S., Brodal, G. S. & Mailund, T. (2013). Algorithms for Computing the Triplet and Quartet Distances for Binary and General Trees. Biology, 2(4), 1189-1209. https://doi.org/10.3390/biology2041189

Böhm, M., Fazzone, A., Leonardi, S., Menghini, C. & Schwiegelshohn, C. (2021). Algorithms for fair k-clustering with multiple protected attributes. Operations Research Letters, 49(5), 787-789. https://doi.org/10.1016/j.orl.2021.08.011

Barnabo, G., Leonardi, S., Fazzone, A. & Schwiegelshohn, C. (2019). Algorithms for fair team formation in online labour marketplaces. The Web Conference 2019 - Companion of the World Wide Web Conference, WWW 2019, 484-490. https://doi.org/10.1145/3308560.3317587

Brodal, G. S. & Jørgensen, A. G. (2007). A Linear Time Algorithm for the k Maximal Sums Problem. In L. Kucera & A. Kucera (Eds.), Mathematical Foundations of Computer Science 2007: 32nd International Symposium, MFCS 2007 Ceský Krumlov, Czech Republic, August 26-31, 2007 Proceedings (pp. 442-453). Springer. https://doi.org/10.1007/978-3-540-74456-6_40

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

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., 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

Wilkinson, B. T. (2014). Amortized bounds for dynamic orthogonal range reporting. In A. S. Schulz & D. Wagner (Eds.), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (pp. 842-856). Springer. https://doi.org/10.1007/978-3-662-44777-2_69

Ejrnæs, R., Moeslund, J. E. & Bladt, J., (2014). Analyse om omfang af biodiversitet repræsenteret i de udpegede Natura 2000 områder på land, 16 p., Notat fra DCE - Nationalt Center for Miljø og Energi (2011-2019)

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., 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

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., 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

Caragiannis, I., Larsen, K. G. & Shyam, S. (2026). A New Lower Bound for Multicolor Discrepancy with Applications to Fair Division. In R. Lavi & J. Zhang (Eds.), Algorithmic Game Theory: 18th International Symposium, SAGT 2025, Bath, UK, September 2–5, 2025, Proceedings (pp. 228-246). Springer. https://doi.org/10.1007/978-3-032-03639-1_13

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

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

Brodal, G. S., Georgiadis, L. & Katriel, I. (2008). An O(n log n) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree. Operations Research Letters, 36(1), 14 -18. https://doi.org/10.1016/j.orl.2007.02.012

Arge, L., Brodal, G. S., Truelsen, J. & Tsirogiannis, C. (2013). An optimal and practical cache-oblivious algorithm for computing multiresolution rasters. In Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (pp. 61-72). Springer VS. https://doi.org/10.1007/978-3-642-40450-4_6

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

Brodal, G. S., Träff, J. L. & Zaroliagis, C. D. (1998). A Parallel Priority Queue with Constant Time Operations. Journal of Parallel and Distributed Computing, 49(1), 4-21. https://doi.org/10.1006/jpdc.1998.1425

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 (2011-2019)

Afshani, P., Berglin, E., Van Duijn, I. & Nielsen, J. S. (2016). Applications of incidence bounds in point covering problems. In S. Fekete & A. Lubiw (Eds.), 32nd International Symposium on Computational Geometry, SoCG 2016 (Vol. 51, pp. 60.1-60.15). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.60

Brodal, G. S. & Gasieniec, L. (1996). Approximate dictionary queries. In D. Hirschberg & G. Myers (Eds.), Combinatorial Pattern Matching: 7th Annual Symposium, CPM 96 Laguna Beach, California, June 10–12, 1996 Proceedings (pp. 65-74). Springer. https://doi.org/10.1007/3-540-61258-0_6

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

Afshani, P., Agarwal, P. K., Arge, L. A., Larsen, K. G. & Phillips, J. M. (2011). (Approximate) Uncertain Skylines. In Proceedings of the 14th International Conference on Database Theory (pp. 186-196). Association for Computing Machinery. https://doi.org/10.1145/1938551.1938576

Afshani, P., Agarwal, P. K., Arge, L., Larsen, K. G. & Phillips, J. (2013). (Approximate) Uncertain Skylines. Theory of Computing Systems, 52(3), 342-366. https://doi.org/10.1007/s00224-012-9382-7

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

Bringmann, K., Larsen, K. G., Nusser, A., Rotenberg, E. & Wang, Y. (2025). Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation. In O. Aichholzer & H. Wang (Eds.), 41st International Symposium on Computational Geometry (SoCG 2025) (Vol. 332, pp. 25:1-25:16). Article 25 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2025.25

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

Sand, A., Pedersen, C. N. S., Mailund, T., Brodal, G. S. & Fagerberg, R. (2013). A practical O(n log² n) time algorithm for computing the triplet distance on binary trees. BMC Bioinformatics, 14(Suppl 2), S18. https://doi.org/10.1186/1471-2105-14-S2-S18

Displaying results 1 to 50 out of 456

Revised 01.09.2025

Publications

Head of research