Department of Computer Science
Mikko Koivisto's home page / Publications

Contact | Publications | Research | Software | Teaching

Publications

Algorithm theory in the conferences FOCS, STOC, SODA, COLT, ICALP, ESA, STACS, I(W)PEC, ISIT, SAT, WG, COCOON. Machine learning, artificial intelligence, and bioinformatics in the conferences ICML, NIPS, UAI, AAAI, IJCAI, AISTATS, ECML, ALT, WABI, PSB. In addition, direct journal publications in all these areas, plus journalizations of conference publications. For citations, see my profile at Google Scholar. For open access copies and links to many of the articles (especially the most recent ones), see the archive.

New peer-reviewed publications to appear

  1. Exact sampling of directed acyclic graphs from modular distributions
    Topi Talvitie, Aleksis Vuoksenmaa, and Mikko Koivisto
    UAI 2019 (Best Student Paper Award)
  2. On structure priors for learning Bayesian networks
    Ralf Eggeling, Jussi Viinikka, Aleksis Vuoksenmaa, and Mikko Koivisto
    AISTATS 2019
  3. Counting and sampling Markov equivalent directed acyclic graphs
    Topi Talvitie and Mikko Koivisto
    AAAI 2019

Selected Yearly Highlights

  1. A scalable scheme for counting linear extensions
    Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2018
  2. The mixing of Markov chains on linear extensions in practice
    Topi Talvitie, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2017
  3. Counting linear extensions of sparse posets
     Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2016
  4. Dealing with small data: On the generalization of context trees
     Ralf Eggeling, Mikko Koivisto, and Ivo Grosse
    ICML 2015
  5. Predicting the hardness of learning Bayesian networks
     Brandon Malone, Kustaa Kangas, Matti Järvisalo, Mikko Koivisto, and Petri Myllymäki
    AAAI 2014
  6. Annealed importance sampling for structure learning in Bayesian networks
    Teppo Niinimäki and Mikko Koivisto
    IJCAI 2013
  7. Fast zeta transforms for lattices with few irreducibles
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
    SODA 2012
  8. Partial order MCMC for structure discovery in Bayesian networks
    Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto
    UAI 2011
  9. A space-time tradeoff for permutation problems
    Mikko Koivisto and Pekka Parviainen
    SODA 2010
  10. Exact structure discovery in Bayesian networks with less space
    Pekka Parviainen and Mikko Koivisto
    UAI 2009 (The runner up for the Best Student Paper Award. Journal version in JMLR 14 (2013) 1387-1415.)
  11. Computing the Tutte polynomial in vertex-exponential time
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    FOCS 2008
  12. Fourier meets Möbius: fast subset convolution
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    STOC 2007
  13. An O*(2n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion
    Mikko Koivisto
    FOCS 2006 (Journal version in SIAM J. Comput. 39 (2009) 546-563.)
  14. A hidden Markov technique for haplotype reconstruction
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    WABI 2005
  15. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research 5 (2004) 549-573.
  16. An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries
    Mikko Koivisto, Markus Perola, Teppo Varilo, William Hennah, Jesper Ekelund, Margus Lukk, Leena Peltonen, Esko Ukkonen, and Heikki Mannila
    PSB 2003

Peer-reviewed publications

  1. On the number of connected sets in bounded-degree graphs
    Kustaa Kangas, Petteri Kaski, Mikko Koiviso, and Janne Korhonen
    Electr. J. Comb.
  2. Counting connected subgraphs with maximum-degree-aware sieving
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    ISAAC 2018
  3. Algorithms for learning parsimonious context trees
    Ralf Eggeling, Mikko Koivisto, and Ivo Grosse
    Machine Learning
  4. Finding optimal Bayesian networks with local structure
    Topi Talvitie, Ralf Eggeling, and Mikko Koivisto
    PGM 2018
  5. NP-completeness results for partitioning a graph into total dominating sets
    Mikko Koivisto, Petteri Laakkonen, and Juho Lauri
    Theoretical Computer Science
  6. A faster tree-decomposition based algorithm for counting linear extensions
    Sami Salonen, Kustaa Kangas, and Mikko Koivisto
    IPEC 2018
  7. A scalable scheme for counting linear extensions
    Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2018
  8. Intersection-validation: A method for evaluating structure learning without ground truth
    Jussi Viinikka, Ralf Eggeling, and Mikko Koivisto
    AISTATS 2018
  9. Counting linear extensions in practice: MCMC versus exponential Monte Carlo
    Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto
    AAAI 2018
  10. NP-completeness results for partitioning a graph into total dominating sets
    Mikko Koivisto, Petteri Laakkonen, and Juho Lauri
    COCOON 2017
  11. The mixing of Markov chains on linear extensions in practice
    Topi Talvitie, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2017
  12. Sharper upper bounds for unbalanced uniquely decodable code pairs
    Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof
    IEEE Transactions on Information Theory (Preliminary version at ISIT 2016)
  13. Narrow sieves for parameterized paths and packings
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Journal of Computer and System Sciences (Preliminary version: arXiv 1007.1161)
  14. Pruning rules for learning parsimonious context trees
     Ralf Eggeling and Mikko Koivisto
    UAI 2016
  15. Counting linear extensions of sparse posets
     Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2016
  16. Sharper upper bounds for unbalanced uniquely decodable code pairs
    P. Austrin, P. Kaski, M. Koivisto, and J. Nederlof
    The 2016 IEEE International Symposium on Information Theory (ISIT 2016) pp. 335-339, IEEE, 2016
  17. Structure discovery in Bayesian neworks by sampling partial orders
     T. Niinimäki, P. Parviainen, and M. Koivisto
    Journal of Machine Learning Research 17 (2016) 1-47 (Preliminary versions at AISTATS 2010, UAI 2011, IJCAI 2013)
  18. Separating OR, SUM, and XOR circuits
    M. Find, M. Göös, M. Järvisalo, P. Kaski, M. Koivisto, and J. H. Korhonen
    Journal of Computer and System Sciences 82 (2016) 793-801 (Preliminary version at SAT 2012)
  19. Dense Subset Sum may be the hardest
    P. Austrin, P. Kaski, M. Koivisto, and J. Nederlof
    33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), LIPIcs 47, pp. 13:1-13:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016
  20. Averaging of decomposable graphs by dynamic programming and sampling
    K. Kangas, T. Niinimäki, and M. Koivisto
    31st Conf. on Uncertainty in Artificial Intelligence (UAI 2015)
  21. On finding optimal polytrees
    S. Gaspers, M. Koivisto, M. Liedloff, S. Ordyniak, and S. Szeider
    Theoretical Computer Science 592 (2015) 49-58 (Preliminary version at AAAI 2012)
  22. Dealing with small data: On the generalization of context trees
     Ralf Eggeling, Mikko Koivisto, and Ivo Grosse
    Internat. Conf. on Machine Learning 2015 (ICML 2015)
  23. Subset Sum in the absence of concentration
    P. Austrin, P. Kaski, M. Koivisto, and J. Nederlof
    32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), LIPIcs 30, pp. 48-61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015
  24. Learning chordal Markov networks by dynamic programming
    K. Kangas, T. Niinimäki, and M. Koivisto
    Advances in Neural Information Processing Systems 27 (NIPS 2014), pp. 2357-2365, 2014
  25. On the number of connected sets in bounded degree graphs
    K. Kangas, P. Kaski, M. Koivisto, and J. H. Korhonen
    40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), LNCS 8747, pp. 336-347, Springer, 2014
  26. Predicting the hardness of learning Bayesian networks
    B. Malone, K. Kangas, M. Järvisalo, M. Koivisto, and P. Myllymäki
    28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 2460-2466, AAAI, 2014
  27. Fast monotone summation over disjoint sets
    P. Kaski, M. Koivisto, J. H. Korhonen, and I. S. Sergeev
    Information Processing Letters 114 (2014) 264-267
  28. Treedy: a heuristic for counting and sampling subsets
    T. Niinimäki and M. Koivisto
    UAI 2013
  29. Fast zeta transforms for lattices with few irreducibles
    A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, J. Nederlof, and P. Parviainen
    ACM Transactions on Algorithms 12 (2015) 4:1-17
  30. Finding optimal Bayesian networks using precedence constraints
    P. Parviainen and M. Koivisto
    Journal of Machine Learning Research 14 (2013) 1387-1415
  31. Annealed importance sampling for structure learning in Bayesian networks
    T. Niinimäki and M. Koivisto
    IJCAI 2013
  32. Space-time tradeoffs for Subset Sum: an improved worst case algorithm
    P. Austrin, P. Kaski, M. Koivisto, and J. Määttä
    ICALP 2013
  33. Fast monotone summation over disjoint sets
    P. Kaski, M. Koivisto, and J. Korhonen
    7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS 7535, pp. 159-170, Springer, 2012
  34. Homomorphic hashing for sparse coefficient extraction
    P. Kaski, M. Koivisto, and J. Nederlof
    7th International Symposium on Parameterized and Exact Computation (IPEC 2012), LNCS 7535, pp. 147-158, Springer, 2012 arXiv 1203.4063
  35. Finding efficient circuits for ensemble computation
    M. Järvisalo, P. Kaski, M. Koivisto, and J. Korhonen
    15th International Conference on Theory and Applications of Satisfiability Testing (SAT 2012), LNCS 7317, pp. 369-382, Springer, 2012
  36. On finding optimal polytrees
    S. Gaspers, M. Koivisto, M. Liedloff, S. Ordyniak, and S. Szeider
    26th AAAI Conference on Artificial Intelligence (AAAI 2012), pp. 750-756, AAAI, 2012
  37. The traveling salesman problem in bounded degree graphs
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    ACM Transactions on Algorithms 8 (2012, Article 18) 1-13
  38. Fast zeta transforms for lattices with few irreducibles
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
    23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1436-1444, SIAM, 2012
  39. Covering and packing in linear space
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Information Processing Letters 111 (2011) 1033-1036
  40. Ancestor relations in the presence of unobserved variables
    Pekka Parviainen and Mikko Koivisto
    The European Conf. on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2011), LNCS 6912, pp. 581-596, Springer, 2010
  41. Partial order MCMC for structure discovery in Bayesian networks
    Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto
    27th Conf. on Uncertainty in Artificial Intelligence (UAI 2011), AUAI Press, pp. 447-564, 2011
  42. Evaluation of permanents in rings and semirings
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Information Processing Letters, 110: 867-870, 2010. A preliminary version: arXiv 0904.3251
  43. Covering and packing in linear space
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    37th Internat. Colloq. on Automata, Languages and Programming (ICALP 2010), LNCS 6198, pp. 727-737, Springer, 2010
  44. Trimmed Moebius inversion and graphs of bounded degree
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Theory of Computing Systems 47 (2010) 637-654
  45. Bayesian structure discovery in Bayesian networks with less space
    Pekka Parviainen and Mikko Koivisto
    13th Internat. Conf. on Artificial Intelligence and Statistics (AISTATS 2010), Volume 9 of JMLR: W&CP 9, pp. 589-596, 2010
  46. A space-time tradeoff for permutation problems
    Mikko Koivisto and Pekka Parviainen
    21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 484-492, SIAM, 2010
  47. Partitioning into sets of bounded cardinality
    Mikko Koivisto
    4th Internat. Workshop on Parameterized and Exact Computation (IWPEC 2009), LNCS 5917, pp. 258-263, Springer, 2009
  48. Mixture model clustering of phenotype features reveals evidence for association of DTNBP1 to a specific subtype of schizophrenia
    Jaana Wessman, Tiina Paunio, Annamari Tuulio-Henriksson, Mikko Koivisto, Timo Partonen, Jaana Suvisaari, Joni A. Turunen, Juho Wedenoja, William Hennah, Olli Pietil\E4inen, Jouko L\F6nnqvist, Heikki Mannila, Leena Peltonen
    Biological psychiatry 66 (2009) 990-996
  49. Set partitioning via inclusion-exclusion
    Andreas Björklund, Thore Husfeldt, and Mikko Koivisto
    SIAM Journal on Computing, special issue dedicated to selected papers from FOCS 2006, 39 (2009) 546-563 Online version.
  50. Counting paths and packings in halves
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    17th Annual European Symposium on Algorithms (ESA 2009), LNCS 5757, pp. 578-586, Springer, 2009 arXiv 0904.3093.
  51. Exact structure discovery in Bayesian networks with less space
    Pekka Parviainen and Mikko Koivisto
    25th Conf. on Uncertainty in Artificial Intelligence (UAI 2009). pp 436-443, AUAI, 2009 (the runner up for the Best Student Paper Award)
  52. Computing the Tutte polynomial in vertex-exponential time
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 677-686, IEEE Computer Society, 2008, arXiv 0711.2585
  53. Fast Bayesian haplotype inference via context tree weighting
    Pasi Rastas, Jussi Kollin, and Mikko Koivisto
    Algorithms in Bioinformatics: 8th Internat. Workshop (WABI 2008), LNCS 5251, pp. 259-270, Springer, 2008
  54. The Travelling Salesman Problem in bounded degree graphs
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    35th Internat. Colloq. on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 198-209, Springer, 2008
  55. Trimmed Moebius inversion and graphs of bounded degree
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Proceedings of the 25th Internat. Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 85-96, 2008
  56. Phasing genotypes using a hidden Markov model
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    In: I. Mandoiu and A. Zelikovsky (eds.), Bioinformatics Algorithms: Techniques and Applications, pp. 373-391, Wiley, 2008
  57. Fourier meets Möbius: fast subset convolution
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    39th ACM Symposium on Theory of Computing (STOC 2007), pp. 67-74, ACM Press, 2007
  58. An O*(2^n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion
    Mikko Koivisto
    47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583-590, IEEE Computer Society, 2006
  59. Bayesian learning with mixtures of trees
    Jussi Kollin and Mikko Koivisto
    17th European Conf. on Machine Learning (ECML 2006), LNCS 4212, pp. 294-305, Springer, 2006
  60. Advances in exact Bayesian structure discovery in Bayesian networks.
    Mikko Koivisto
    22nd Conf. on Uncertainty in Artificial Intelligence (UAI 2006), pp. 241-248, AUAI Press, 2006 (computer program REBEL available)
  61. Parent assignment is hard for the MDL, AIC, and NML costs
    Mikko Koivisto
    19th Annual Conf. on Learning Theory (COLT 2006), LNAI 4005, pp. 289-303, Springer, 2006
  62. Optimal 2-constraint satisfaction via sum-product algorithms
    Mikko Koivisto
    Information Processing Letters 98 (2006) 22-24 [ScienceDirect]
  63. A hidden Markov technique for haplotype reconstruction
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    In: R. Casadio and G. Myers (eds.), Algorithms in Bioinformatics: 5th Internat. Workshop (WABI 2005), LNCS 3692, pp. 140-151, Springer, 2005 (computer program HIT available)
  64. Computational aspects of Bayesian partition models
    Mikko Koivisto and Kismat Sood
    Internat. Conf. on Machine Learning 2005 (ICML 2005), pp. 433-440, ACM Press, 2005
  65. Hidden Markov modelling techniques for haplotype analysis
    Mikko Koivisto, Teemu Kivioja, Pasi Rastas, Heikki Mannila, and Esko Ukkonen
    In: S. Ben-David, J. Case, and A. Maruoka (eds.), Algorithmic Learning Theory: 15th International Conference (ALT 2004), LNCS 3244, pp. 37-52, Springer, 2004
  66. Recombination systems
    Mikko Koivisto, Pasi Rastas, and Esko Ukkonen
    In: J. Karhumaki, H. Maurer, G. Paun, G. Rozenberg (eds.), Theory is Forever (Salomaa Festschrift), LNCS 3113, pp. 159-169, Springer-Verlag, Berlin, Heidelberg, 2004
  67. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research, 5(May):549-573, 2004
  68. An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries
    Mikko Koivisto, Markus Perola, Teppo Varilo, William Hennah, Jesper Ekelund, Margus Lukk, Leena Peltonen, Esko Ukkonen, and Heikki Mannila
    Pacific Symposium on Biocomputing 2003 (PSB 2003), pp. 502-513, World Scientific, 2002 (computer program MDLBlockFinder available)
  69. Offspring risk and sibling risk for multilocus traits
    Mikko Koivisto and Heikki Mannila
    Human Heredity, 51(4):209-216, 2001

Theses

  1. Ph.D. thesis: Sum-Product Algorithms for the Analysis of Genetic Risks. Department of Computer Science, University of Helsinki, Report A 2004-1, January 2004. Supervisor: Heikki Mannila.
  2. M.Sc. thesis (in Finnish): Sukulaisriskien laskenta ja k\E4ytt\F6 geneettisten mallien arvioinnissa (Computation of recurrence risks and the analysis of genetic models). Department of Computer Science, University of Helsinki, Report C 2000-52, August 2000. (Awarded a Pro Gradu prize by the Faculty of Science.) Supervisor: Heikki Mannila.

Contact | Publications | Research | Software | Teaching

Last modified Aug 16, 2019.