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. Computational statistics, machine learning, and bioinformatics in the conferences ICML, UAI, AAAI, AISTATS, ECML, ALT, WABI, PSB. In addition, direct journal publications in all these areas, plus journalizations of conference publications. For citations, see my profiles at Google Scholar and Microsoft Academic Search.

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

New refereed publications to appear

  1. Fast monotone summation over disjoint sets
    P. Kaski, M. Koivisto, and J. Korhonen
    IPEC 2012
  2. Homomorphic hashing for sparse coefficient extraction
    P. Kaski, M. Koivisto, and J. Nederlof
    IPEC 2012 arXiv 1203.4063
  3. Finding efficient circuits for ensemble computation
    M. Järvisalo, P. Kaski, M. Koivisto, and J. Korhonen
    SAT 2012
  4. On finding optimal polytrees
    S. Gaspers, M. Koivisto, M. Liedloff, S. Ordyniak, and S. Szeider
    AAAI 2012

New unrefereed reports

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

Selected Yearly Highlights

  1. Fast zeta transforms for lattices with few irreducibles
    A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, J. Nederlof, and P. Parviainen
    SODA 2012
  2. Partial order MCMC for structure discovery in Bayesian networks
    Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto
    UAI 2011
  3. A space-time tradeoff for permutation problems
    Mikko Koivisto and Pekka Parviainen
    SODA 2010
  4. 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.)
  5. Computing the Tutte polynomial in vertex-exponential time
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    FOCS 2008
  6. Fourier meets Möbius: fast subset convolution
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    STOC 2007
  7. 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.)
  8. A hidden Markov technique for haplotype reconstruction
    Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen
    WABI 2005
  9. Exact Bayesian structure discovery in Bayesian networks
    Mikko Koivisto and Kismat Sood
    Journal of Machine Learning Research 5 (2004) 549-573.
  10. 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

Refereed publications

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

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

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

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

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

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

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

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

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

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

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

  12. 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äinen, Jouko Lönnqvist, Heikki Mannila, Leena Peltonen
    Biological psychiatry 66 (2009) 990-996

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  33. 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äyttö 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 Oct 3, 2012.