Aarhus University Seal

Publications

Search for publications at Department of Computer Science

Below you find a complete list of publications published and edited by scientists at the Department of Computer Science

Sort by: Date | Author | Title

Emiris, I. Z., Mourrain, B. & Tsigaridas, E. (2010). The DMM Bound: Multivariate (Aggregrate) Separation Bounds. International Symposium on Symbolic and Algebraic Computation, 243-250. https://doi.org/10.1145/1837934.1837981
Halasz, F., Schwartz, M., Grønbæk, K. (Ed.) & Trigg, R. H. (Ed.) (1994). The Dexter hypertext reference model. Association for Computing Machinery. Communications, 37(2), 30-39. https://doi.org/10.1145/175235.175237
Møller, A. & Schwartzbach, M. I. (2005). The Design Space of Type Checkers for XML Transformation Languages. In Database Theory - ICDT 2005: 10th International Conference, Edinburgh, UK, January 5-7, 2005. Proceedings (pp. 17-36). Springer. https://doi.org/10.1007/978-3-540-30570-5_2
Jensen, K. (1985). The Design of a Program Package for an Introductory Petri Net Course. In G. Rozenberg, H. Genrich & G. Roucairol (Eds.), Advances in Petri Nets 1984 (Vol. 188, pp. 259-266). Springer. https://doi.org/10.1007/3-540-15204-0_15
Bødker, S. & Buur, J. (2002). The Design Collaboratorium - a place for usability design. ACM Transactions on Computer-Human Interaction, 9(2), 152-169. https://doi.org/10.1145/513665.513670
Vermeulen, J., Lim, B. Y., Avdic, M., Wang, D. & Abdul, A. (2019). The Curious Case of Providing Intelligibility for Smart Speakers. Abstract from The 2019 ACM CHI Conference on Human Factors in Computing Systems (CHI'19), Glasgow, United Kingdom.
Gambs, S., Ranellucci, S. & Tapp, A. (2015). The crypto-democracy and the trustworthy (position paper). In Data Privacy Management, Autonomous Spontaneous Security, and Security Assurance: 9th International Workshop, DPM 2014, 7th International Workshop, SETOP 2014, and 3rd International Workshop, QASA 2014, Wroclaw, Poland, September 10-11, 2014. Revised Selected Papers (Vol. 8872, pp. 58-76). Springer VS. https://doi.org/10.1007/978-3-319-17016-9_5
Gambs, S., Ranellucci, S. & Tapp, A. (2014). The Crypto-democracy and the Trustworthy. Paper presented at Data Privacy Management, Wroclaw, Poland. http://arxiv.org/pdf/1409.2432v1.pdf
Bender, M. A., Brodal, G. S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J. & López-Ortiz, A. (2003). The Cost of Cache-Oblivious Searching. In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS): IEEE Computer Society Press, Washington D.C. (Vol. Session 6, pp. 271-282). IEEE Computer Society Press.
Bender, M. A., Brodal, G. S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J. & López-Ortiz, A. (2011). The Cost of Cache-Oblivious Searching. Algorithmica, 61(2), 463-505. https://doi.org/10.1007/s00453-010-9394-0
Engelfriet, J. & Skyum, S. (1982). The copying power of one-state tree transducers. Journal of Computer and System Sciences, 25(3), 418-435. https://doi.org/10.1016/0022-0000(82)90019-8
Lyngsø, R. B. & Pedersen, C. N. S. (2002). The Consensus String Problem and the Complexity of Comparing Hidden Markov Models. Journal of Computer and System Sciences, 65(3), 545-569.
Buss, J. F., Frandsen, G. S. & Shallit, J. O. (1999). The Computational Complexity of Some Problems of Linear Algebra. Journal of Computer and System Sciences, 58(3), 572-596. https://doi.org/10.1006/jcss.1998.1608
Buss, J. F., Frandsen, G. S. & Shallit, J. O. (1997). The computational complexity of some problems of linear algebra. In R. Reischuk & M. Morvan (Eds.), STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science Lübeck, Germany February 27–March 1, 1997 Proceedings (pp. 451-462). Springer. https://doi.org/10.1007/BFb0023480
Miltersen, P. B. (2005). The Computational Complexity of One-Dimensional Sandpiles. In S. B. Cooper, B. Löwe & L. Torenvliet (Eds.), New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam, The Netherlands, June 8-12, 2005. Proceedings (pp. 342-350). Springer. https://doi.org/10.1007/11494645_42
Olsen, M. (2008). The Computational Complexity of Link Building. Lecture Notes in Computer Science, 5092, 119-129.
Shi, Z., Møldrup, L., Mathur, U. & Pavlogiannis, A. (2026). The Complexity of Testing Message-Passing Concurrency. Proceedings of the ACM on Programming Languages , 10, 1-32. https://doi.org/10.1145/3776643
Miltersen, P. B., Gurvich, V. & Andersson, D. (2008). The Complexity of Solving Stochastic Games on Graphs. Department of Computer Science, Aarhus University. http://www.daimi.au.dk/~bromille/Papers/mean.pdf
Axelsson, R., Lange, M. & Somla, R. (2007). The Complexity of Model Checking Higher-Order Fixpoint Logic. Logical Methods in Computer Science, 3(2). http://arxiv.org/pdf/0704.3931
Miltersen, P. B. (1993). The complexity of malign measures. S I A M Journal on Computing, 22(1), 147-156. https://doi.org/10.1137/0222012
Miltersen, P. B. (1991). The complexity of malign ensembles. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991. (pp. 164-171). IEEE Computer Society Press. https://doi.org/10.1109/SCT.1991.160257
Caragiannis, I. & Fehrs, K. (2022). The Complexity of Learning Approval-Based Multiwinner Voting Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4925-4932. https://doi.org/10.1609/aaai.v36i5.20422
Hansen, T. D. & Ibsen-Jensen, R. (2013). The complexity of interior point methods for solving discounted turn-based stochastic games. In The Nature of Computation, Logic, Algorithms, Applications: 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Proceedings (pp. 252-262). Springer VS. https://doi.org/10.1007/978-3-642-39053-1_29
Frandsen, G. S., Miltersen, P. B. & Skyum, S. (1993). The complexity of finding replicas using equality tests. In A. M. Borzyszkowsji & S. Sokolowski (Eds.), Mathematical Foundations of Computer Science 1993: 18th International Symposium, MFCS'93 Gdansk, Poland, August 30-September 3, 1993 Proceedings (pp. 463-472). Springer. https://doi.org/10.1007/3-540-57182-5_38
Fortune, S., Hopcroft, J. & Schmidt, E. M. (1978). The complexity of equivalence and containment for free single variable program schemes. In G. Ausiello & C. Böhm (Eds.), Automata, Languages and Programming: Fifth Colloquium, Udine, Italy, July 17–21, 1978 (pp. 227-240). Springer. https://doi.org/10.1007/3-540-08860-1_17
Mathur, U., Pavlogiannis, A. & Viswanathan, M. (2020). The Complexity of Dynamic Data Race Prediction. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 (pp. 713–727). Article 3394783 Association for Computing Machinery. https://doi.org/10.1145/3373718.3394783
Brodal, G. S., Fagerberg, R., Pedersen, C. N. S. & Östlin, A. (2001). The Complexity of Constructing Evolutionary Trees Using Experiments. In F. Orejas, P. G. Spirakis & J. van Leeuwen (Eds.), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings (pp. 140-151). Springer. https://doi.org/10.1007/3-540-48224-5_12
Brodal, G. S., Fagerberg, R., Pedersen, C. N. S., Östlin, A., Orejas, F. (Ed.), Spirakis, P. G. (Ed.) & Leeuwen, J. V. (Ed.) (2001). The Complexity of Constructing Evolutionary Trees Using Experiments. In Lecture Notes In Computer Science; Vol. 2076: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (2076 of Lecture Notes in Computer Science ed., Vol. 2076/2001, pp. 140-151). Springer.
Etessami, K., Hansen, K. A., Miltersen, P. B. & Sørensen , T. B. (2014). The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form. In R. Lavi (Ed.), Algorithmic Game Theory: 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 – October 2, 2014. Proceedings (pp. 231-243 ). Springer VS. https://doi.org/10.1007/978-3-662-44803-8_20
Ghosh, S. & Simkin, M. (2019). The Communication Complexity of Threshold Private Set Intersection. In A. Boldyreva & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings (Vol. II, pp. 3-29). Springer. https://doi.org/10.1007/978-3-030-26951-7_1
Huang, Z. & Yi, K. (2014). The communication complexity of distributed epsilon-approximations. In D. Shmoys (Ed.), 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 591-600). IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2014.69
Evangelista, S., Westergaard, M. & Kristensen, L. M. (2008). The ComBack Method Revisited: Caching Strategies and Extension with Delayed Duplicate Detection. In Ninth Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN Tools (pp. 63-82). Department of Computer Science.
Westergaard, M., Kristensen, L. M., Brodal, G. S. & Arge, L. (2007). The ComBack Method - Extending Hash Compaction with Backtracking. In Petri Nets and Other Models of Concurrency – ICATPN 2007: 28th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2007, Siedlce, Poland, June 25-29, 2007. Proceedings (pp. 455-464). Springer. https://doi.org/10.1007/978-3-540-73094-1_26
Ehn, P. & Kyng, M. (1987). The Collective Resource Approach to Systems Design. In G. Bjerknes, P. Ehn & M. Kyng (Eds.), Computers and Democracy - a Scandinavian Challenge (pp. 17-58). Gower Publishing.
Brody, J. & Verbin, E. (2010). The Coin Problem  and Pseudorandomness for Branching Programs. In 51st Annual IEEE Symposium on Foundations of Computer Science. FOCS 2010 (pp. 30-39). IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2010.10
Kranen, P., Assent, I., Baldauf, C. & Seidl, T. (2011). The ClusTree : indexing micro-clusters for anytime stream mining. Knowledge and Information Systems, 29(2), 249-272. https://doi.org/10.1007/s10115-010-0342-8
Bahr, P., Grathwohl, H. B. & Møgelberg, R. E. (2017). The clocks are ticking: No more delays! In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 Article 8005097 IEEE. https://doi.org/10.1109/LICS.2017.8005097
Satyanarayan, A., Strazzulla, D., Klokmose, C. N., Beaudouin-Lafon, M. & Mackay, W. (2013). The CHI 2013 interactive schedule. In W. E. Mackay, S. Brewster & S. Brewster (Eds.), CHI EA '13 CHI '13 Extended Abstracts on Human Factors in Computing Systems (pp. 2987-2990). Association for Computing Machinery. https://doi.org/10.1145/2468356.2479591
Damgård, I. B., Faust, S., Mukherjee, P. & Venturi, D. (2015). The Chaining Lemma and its application. In A. Lehmann & S. Wolf (Eds.), Information Theoretic Security: 8th International Conference, ICITS 2015, Lugano, Switzerland, May 2-5, 2015. Proceedings (pp. 181-196). Springer VS. https://doi.org/10.1007/978-3-319-17470-9_11