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, IWPEC. Computational statistics in the conferences ICML, UAI, AISTATS, ECML, ALT. Bioinformatics in the conferences WABI, PSB. In addition, direct journal publications in all the three areas. Plus journalizations of conference publications of course.

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

Selected Yearly Highlights

  1. Fast zeta transforms for lattices with few irreducibles
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka 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

New unrefereed reports

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

Refereed publications to appear

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

  2. Covering and packing in linear space
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    Information Processing Letters

  3. Ancestor relations in the presence of unobserved variables
    Pekka Parviainen and Mikko Koivisto
    The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2011)

  4. The Travelling Salesman Problem in bounded degree graphs
    Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
    ACM Transactions on Algorithms

Refereed publications

  1. Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto: Partial order MCMC for structure discovery in Bayesian networks. 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011).

  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Evaluation of permanents in rings and semirings. Information Processing Letters, 110: 867-870, 2010. A preliminary version: arXiv 0904.3251.

  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Covering and packing in linear space. 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), LNCS 6198, pp. 727-737, Springer, 2010.

  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Trimmed Moebius inversion and graphs of bounded degree. Theory of Computing Systems, 47: 637-654, 2010.

  5. Pekka Parviainen and Mikko Koivisto: Bayesian structure discovery in Bayesian networks with less space. 13th International Conference on Artificial Intelligence and Statistics (AISTATS 2010), Volume 9 of JMLR: W&CP 9, pp. 589-596.

  6. Mikko Koivisto and Pekka Parviainen: A space-time tradeoff for permutation problems. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 484-492, SIAM, 2010.

  7. Mikko Koivisto: Partitioning into sets of bounded cardinality. 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009), LNCS 5917, pp. 258-263, Springer, 2009.

  8. 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: Mixture model clustering of phenotype features reveals evidence for association of DTNBP1 to a specific subtype of schizophrenia. Biological psychiatry, 66: 990-996, 2009.

  9. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto: Set partitioning via inclusion-exclusion. SIAM Journal on Computing, special issue dedicated to selected papers from FOCS 2006, 39(2): 546-563, 2009. Online version.

  10. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Counting paths and packings in halves. In: A. Fiat and P. Sanders (eds.), 17th Annual European Symposium on Algorithms (ESA 2009), LNCS 5757, pp. 578-586, Springer, 2009. arXiv 0904.3093.

  11. Pekka Parviainen and Mikko Koivisto: Exact structure discovery in Bayesian networks with less space. 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009). (The runner up for the Best Student Paper Award.)

  12. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Computing the Tutte polynomial in vertex-exponential time. Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 677-686, IEEE Computer Society, 2008, arXiv 0711.2585.

  13. Pasi Rastas, Jussi Kollin, and Mikko Koivisto: Fast Bayesian haplotype inference via context tree weighting. In: K.A. Crandall and J. Lagergren (eds.), Algorithms in Bioinformatics: 8th International Workshop (WABI 2008), LNCS 5251, pp. 259-270, Springer, 2008.

  14. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: The Travelling Salesman Problem in bounded degree graphs. In: L. Aceto et al. (eds.), 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 198-209, Springer, 2008.

  15. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Trimmed Moebius inversion and graphs of bounded degree. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 85-96, 2008.

  16. Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen: Phasing genotypes using a hidden Markov model. In: I. Mandoiu and A. Zelikovsky (eds.), Bioinformatics Algorithms: Techniques and Applications, pp. 373-391, Wiley, 2008.

  17. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto: Fourier meets Möbius: fast subset convolution. Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pp. 67-74, ACM Press, 2007.

  18. Mikko Koivisto: An O*(2^n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583-590, IEEE Computer Society, 2006.

  19. Jussi Kollin and Mikko Koivisto: Bayesian learning with mixtures of trees. In: J. Fürnkranz, T. Scheffer, and M. Spiliopoulou (eds.), Proceedings of the 17th European Conference on Machine Learning (ECML 2006), LNCS 4212, pp. 294-305, Springer, 2006.

  20. Mikko Koivisto: Advances in exact Bayesian structure discovery in Bayesian networks. In: R. Dechter and T. Richardson (eds.), Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence (UAI 2006), pp. 241-248, AUAI Press, 2006. (A computer program REBEL is available.)

  21. Mikko Koivisto: Parent assignment is hard for the MDL, AIC, and NML costs. In: G. Lugosi and H.U. Simon (eds.), The 19th Annual Conference on Learning Theory (COLT 2006), LNAI 4005, pp. 289-303, Springer, 2006.

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

  23. Pasi Rastas, Mikko Koivisto, Heikki Mannila, and Esko Ukkonen: A hidden Markov technique for haplotype reconstruction. In: R. Casadio and G. Myers (eds.), Algorithms in Bioinformatics: 5th International Workshop (WABI 2005), LNCS 3692, pp. 140-151, Springer, 2005. (A computer program HIT is available.)

  24. Mikko Koivisto and Kismat Sood: Computational aspects of Bayesian partition models. In: L. De Raedt and S. Wrobel (eds.), International Conference on Machine Learning 2005 (ICML 2005), pp. 433-440, ACM Press, 2005.

  25. Mikko Koivisto, Teemu Kivioja, Pasi Rastas, Heikki Mannila, and Esko Ukkonen: Hidden Markov modelling techniques for haplotype analysis. 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.

  26. Mikko Koivisto, Pasi Rastas, and Esko Ukkonen: Recombination systems. 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.

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

  28. Mikko Koivisto, Markus Perola, Teppo Varilo, William Hennah, Jesper Ekelund, Margus Lukk, Leena Peltonen, Esko Ukkonen, and Heikki Mannila: An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. In: R.B. Altman, A.K. Dukner, L. Hunter, T.A. Jung, and T.E. Klein (eds.), Pacific Symposium on Biocomputing 2003 (PSB 2003), pp. 502-513, World Scientific, 2002. (A computer program MDLBlockFinder is available.)

  29. Mikko Koivisto and Heikki Mannila: Offspring risk and sibling risk for multilocus traits. 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 17, 2011.