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. 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. NP-completeness results for partitioning a graph into total dominating sets
    Mikko Koivisto, Petteri Laakkonen, and Juho Lauri
    COCOON 2017
  2. The mixing of Markov chains on linear extensions in practice
    Topi Talvitie, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2017

Selected Yearly Highlights

  1. Counting linear extensions of sparse posets
    Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2016
  2. Dealing with small data: On the generalization of context trees
    Ralf Eggeling, Mikko Koivisto, and Ivo Grosse
    ICML 2015
  3. Predicting the hardness of learning Bayesian networks
    Brandon Malone, Kustaa Kangas, Matti Järvisalo, Mikko Koivisto, and Petri Myllymäki
    AAAI 2014
  4. Annealed importance sampling for structure learning in Bayesian networks
    Teppo Niinimäki and Mikko Koivisto
    IJCAI 2013
  5. Fast zeta transforms for lattices with few irreducibles
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
    SODA 2012
  6. Partial order MCMC for structure discovery in Bayesian networks
    Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto
    UAI 2011
  7. A space-time tradeoff for permutation problems
    Mikko Koivisto and Pekka Parviainen
    SODA 2010
  8. 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.)
  9. Computing the Tutte polynomial in vertex-exponential time
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    FOCS 2008
  10. Fourier meets Möbius: fast subset convolution
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    STOC 2007
  11. 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.)
  12. A hidden Markov technique for haplotype reconstruction
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    WABI 2005
  13. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research 5 (2004) 549-573.
  14. 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. 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)
  2. 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)
  3. Pruning rules for learning parsimonious context trees
    Ralf Eggeling and Mikko Koivisto
    UAI 2016
  4. Counting linear extensions of sparse posets
    Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto
    IJCAI 2016
  5. 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
  6. 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)
  7. 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 Sciences82 (2016) 793-801 (Preliminary version at SAT 2012)
  8. 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
  9. 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)
  10. 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)
  11. 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)
  12. 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
  13. 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
  14. 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
  15. 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
  16. Fast monotone summation over disjoint sets
    P. Kaski, M. Koivisto, J. H. Korhonen, and I. S. Sergeev
    Information Processing Letters 114 (2014) 264-267
  17. Treedy: a heuristic for counting and sampling subsets
    T. Niinimäki and M. Koivisto
    UAI 2013
  18. 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
  19. Finding optimal Bayesian networks using precedence constraints
    P. Parviainen and M. Koivisto
    Journal of Machine Learning Research 14 (2013) 1387-1415
  20. Annealed importance sampling for structure learning in Bayesian networks
    T. Niinimäki and M. Koivisto
    IJCAI 2013
  21. Space-time tradeoffs for Subset Sum: an improved worst case algorithm
    P. Austrin, P. Kaski, M. Koivisto, and J. Määttä
    ICALP 2013
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. Covering and packing in linear space
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Information Processing Letters 111 (2011) 1033-1036
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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.
  39. 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.
  40. 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)
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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)
  50. 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
  51. Optimal 2-constraint satisfaction via sum-product algorithms
    Mikko Koivisto
    Information Processing Letters 98 (2006) 22-24 [ScienceDirect]
  52. 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)
  53. 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
  54. 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
  55. 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
  56. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research, 5(May):549-573, 2004
  57. 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)
  58. 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 Jul 20, 2017.