Department of Computer Science

Aarhus University Seal
 Department of Computer Science Research Algorithms, Data Structures and Foundations of Machine Learning Publications

Publications

Sort by: Title
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. 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 (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://epubs.siam.org/doi/pdf/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 thesis, 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 thesis, 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
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
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://arxiv.org/abs/2005.02530
Sand, A., Pedersen, C. N. S., Mailund, T., Brodal, G. S. & Fagerberg, R. (2013). A practical O(n log2 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
Toftrup, M., Sørensen, S. A., Ciosici, M. R. & Assent, I. (2021). A reproduction of Apple's bi-directional LSTM models for language identification in short strings. (pp. 36-42).
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). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2017.12

Displaying results 1 to 50 out of 446

1

2

3

4

5

6

7

8

9

Next

Head of research

Faculty

Revised 01.09.2025