Yliopiston etusivulle Suomeksi På svenska In English
Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Contact | Publications | Research | Software | Teaching

Algorithm theory in the conferences FOCS, STOC, SODA, COLT, ICALP, ESA, STACS, I(W)PEC, 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.

Please note the articles' copyrights are generally held by their respective publishers, so the preprints below may be downloaded for personal use only.

New peer-reviewed publications to appear

  1. Averaging of decomposable graphs by dynamic programming and sampling
    Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto
    UAI 2015
  2. On finding optimal polytrees
    Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, and Stefan Szeider
    Theoretical Computer Science (Preliminary version at AAAI 2012)
  3. Dealing with small data: On the generalization of context trees
    Ralf Eggeling, Mikko Koivisto, and Ivo Grosse
    ICML 2015

New unrefereed reports and manuscripts under review

  • Narrow sieves for parameterized paths and packings
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    arXiv 1007.1161

Selected Yearly Highlights

  1. Predicting the hardness of learning Bayesian networks
    Brandon Malone, Kustaa Kangas, Matti Järvisalo, Mikko Koivisto, and Petri Myllymäki
    AAAI 2014
  2. Annealed importance sampling for structure learning in Bayesian networks
    Teppo Niinimäki and Mikko Koivisto
    IJCAI 2013
  3. Fast zeta transforms for lattices with few irreducibles
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
    SODA 2012
  4. Partial order MCMC for structure discovery in Bayesian networks
    Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto
    UAI 2011
  5. A space-time tradeoff for permutation problems
    Mikko Koivisto and Pekka Parviainen
    SODA 2010
  6. 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.)
  7. Computing the Tutte polynomial in vertex-exponential time
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    FOCS 2008
  8. Fourier meets Möbius: fast subset convolution
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    STOC 2007
  9. 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.)
  10. A hidden Markov technique for haplotype reconstruction
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    WABI 2005
  11. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research 5 (2004) 549-573.
  12. 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. 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, pp. 48-61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015

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

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

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

  5. Fast monotone summation over disjoint sets
    P. Kaski, M. Koivisto, J. H. Korhonen, and I. S. Sergeev
    Information Processing Letters 114 (2014) 264-267

  6. Treedy: a heuristic for counting and sampling subsets
    T. Niinimäki and M. Koivisto
    UAI 2013

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

  8. Finding optimal Bayesian networks using precedence constraints
    P. Parviainen and M. Koivisto
    Journal of Machine Learning Research 14 (2013) 1387-1415

  9. Annealed importance sampling for structure learning in Bayesian networks
    T. Niinimäki and M. Koivisto
    IJCAI 2013

  10. Space-time tradeoffs for Subset Sum: an improved worst case algorithm
    P. Austrin, P. Kaski, M. Koivisto, and J. Määttä
    ICALP 2013

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

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

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

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

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

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

  17. Covering and packing in linear space
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Information Processing Letters 111 (2011) 1033-1036

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

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

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

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

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

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

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

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

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

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

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

  29. 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)

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

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

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

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

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

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

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

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

  38. 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)

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

  40. Optimal 2-constraint satisfaction via sum-product algorithms
    Mikko Koivisto
    Information Processing Letters 98 (2006) 22-24 [ScienceDirect]

  41. 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)

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

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

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

  45. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research, 5(May):549-573, 2004

  46. 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)

  47. 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 Feb 3, 2016.