Department information

 

Petteri Kaski

D.Sc.(Tech.), Researcher

Contact Information

Helsinki Institute for Information Technology HIIT
Department of Computer Science
P.O. Box 68 (Gustaf Hällströmin katu 2B)
FI-00014 University of Helsinki
Finland

Room: Exactum, A312

Email: petteri.kaski(at)cs.helsinki.fi

Telephone:
+358 9 191 51181 (office)
+358 9 191 51120 (fax)

Research Interests

combinatorial mathematics & algorithms, computational complexity

Teaching

• Linear and bilinear transformations for moderately exponential algorithms (slides, notes), AGAPE 09 Spring School on Fixed Parameter and Exact Algorithms, 25–29 May 2009, Lozari, Corsica.
• Spring 2009 (at Helsinki University of Technology): S-72.2420 / T-79.5203 Graph Theory

Publications

Books

• Classification Algorithms for Codes and Designs, P. Kaski and P. R. J. Östergård, Springer-Verlag, Berlin Heidelberg, 2006.

Journal papers

• There exists no (15,5,4) RBIBD, P. Kaski and P. R. J. Östergård, Journal of Combinatorial Designs 9 (2001), 357–362.
• Enumeration of 2-(9,3,\lambda) designs and their resolutions, P. R. J. Östergård and P. Kaski, Designs, Codes and Cryptography 27 (2002), 131–137. [Design data].
• Classification of resolvable 2-(14,7,12) and 3-(14,7,5) designs, P. Kaski, L. B. Morales, P. R. J. Östergård, D. A. Rosenblueth, and C. Velarde, Journal of Combinatorial Mathematics and Combinatorial Computing 47 (2003), 65–74. [Design data].
• Enumeration of balanced ternary designs, P. Kaski and P. R. J. Östergård, Discrete Applied Mathematics 138 (2004), 133–141. [Design data].
• Miscellaneous classification results for 2-designs, P. Kaski and P. R. J. Östergård, Discrete Mathematics 280 (2004), 65–75. [Design data].
• Packing Steiner trees with identical terminal sets, P. Kaski, Information Processing Letters 91 (2004), 1–5.
• The Steiner triple systems of order 19, P. Kaski and P. R. J. Östergård, Mathematics of Computation 73 (2004), 2075–2092.
• There exist nonisomorphic STS(19) with equivalent point codes, P. Kaski and P. R. J. Östergård, Journal of Combinatorial Designs 12 (2004), 443–448.
• One-factorizations of regular graphs of order 12, P. Kaski and P. R. J. Östergård, Electronic Journal of Combinatorics 12 (2005), R#2.
• Lifetime maximization for multicasting in energy-constrained wireless networks, P. Floréen, P. Kaski, J. Kohonen, and P. Orponen, IEEE Journal on Selected Areas in Communications 23 (2005), 117–126.
• The near resolvable 2-(13,4,3) designs and thirteen-player whist tournaments, H. Haanpää and P. Kaski, Designs, Codes and Cryptography 35 (2005), 271–285.
• Exact and approximate balanced data gathering in energy-constrained sensor networks, P. Floréen, P. Kaski, J. Kohonen, and P. Orponen, Theoretical Computer Science 344 (2005), 30–46.
• Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms, P. Kaski, SIAM Journal on Discrete Mathematics 19 (2005), 664–690.
• Hard satisfiable clause sets for benchmarking equivalence reasoning techniques, H. Haanpää, M. Järvisalo, P. Kaski, and I. Niemelä, Journal on Satisfiability, Boolean Modeling and Computation 2 (2006), 27–46.
• On the coexistence of conference matrices and near resolvable 2-(2k+1,k,k-1) designs, M. Greig, H. Haanpää, and P. Kaski, Journal of Combinatorial Theory, Series A 113 (2006), 703–711. [Design data].
• The Steiner quadruple systems of order 16, P. Kaski, P. R. J. Östergård, and O. Pottonen, Journal of Combinatorial Theory, Series A 113 (2006), 1764–1770.
• There exists no symmetric configuration with 33 points and line size 6, P. Kaski and P. R. J. Östergård, Australasian Journal of Combinatorics 38 (2007), 273–277.
• An enumeration of graphical designs, Y. M. Chee and P. Kaski, Journal of Combinatorial Designs 16 (2008), 70–85. [Design data].
• There are exactly five biplanes with k=11, P. Kaski and P. R. J. Östergård, Journal of Combinatorial Designs 16 (2008), 117–127. [Design data].
• Steiner triple systems of order 19 and 21 with subsystems of order 7, P. Kaski, P. R. J. Östergård, S. Topalova, and R. Zlatarski, Discrete Mathematics 308 (2008) 2732–2741.
• Circumspect descent prevails in solving random constraint satisfaction problems, M. Alava, J. Ardelius, E. Aurell, P. Kaski, S. Krishnamurthy, P. Orponen, and S. Seitz, Proceedings of the National Academy of Sciences of the United States of America 105 (2008) 15253–15257.
• Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs, P. Kaski, A. Penttinen, and J. Suomela, Ad Hoc & Sensor Wireless Networks: An International Journal 6 (2008) 239–263.
• Classification of resolvable balanced incomplete block designs—the unitals on 28 points, P. Kaski and P. R. J. Östergård, Mathematica Slovaca 59 (2009) 121–136. [Design data].
• There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of K_{14}, P. Kaski and P. R. J. Östergård, Journal of Combinatorial Designs 17 (2009) 147–159.
• A catalogue of the Steiner triple systems of order 19, P. Kaski, P. R. J. Östergård, O. Pottonen, and L. Kiviluoto, Bulletin of the Institute of Combinatorics and Its Applications 57 (2009) 35–41.
• Autumn warming and carbon balance of a boreal Scots pine forest in Southern Finland, T. Vesala, S. Launiainen, P. Kolari, J. Pumpanen, S. Sevanto, P. Hari, E. Nikinmaa, P. Kaski, H. Mannila, E. Ukkonen, S. Piao, and P. Ciais, Biogeosciences Discussion 9 (2009) 7053–7081.
• Almost stable matchings by truncating the Gale–Shapley algorithm, P. Floréen, P. Kaski, V. Polishchuk, and J. Suomela, Algorithmica, to appear.

Conference and workshop papers

• Multicast time maximization in energy constrained wireless networks, P. Floréen, P. Kaski, J. Kohonen, and P. Orponen, DIALM-POMC'03 Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing (San Diego, CA, September 19, 2003), ACM, New York, 2003, pp. 50–58.
• Balanced data gathering in energy-constrained sensor networks, E. Falck, P. Floréen, P. Kaski, J. Kohonen, and P. Orponen, Algorithmic Aspects of Wireless Sensor Networks (First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004), Lecture Notes in Computer Science, Vol. 3121, Springer-Verlag, Berlin Heidelberg, 2004, pp. 59–70.
• Nonexistence of perfect Steiner triple systems of orders 19 and 21, P. Kaski, Proceedings of ALCOMA05 (A. Kerber and A. Kohnert, Eds.), Bayreuther Mathematische Schriften 74 (2005), 130–135.
• Engineering an efficient canonical labeling tool for large and sparse graphs, T. Junttila and P. Kaski, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick, Eds.) (New Orleans, January 6, 2007), Society for Industrial and Applied Mathematics, Philadelphia, 2007, pp. 135–149. [Software].
• Fourier meets Möbius: fast subset convolution, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 39th Annual ACM Symposium on Theory of Computing (San Diego, CA, June 11–13, 2007), Association for Computing Machinery, New York, 2007, pp. 67–74.
• A distributed approximation scheme for sleep scheduling in sensor networks, P. Floréen, P. Kaski, and J. Suomela, Proceedings of the 4th Annual IEEE Communications Society Conference on Sensor, Mesh, and Ad Hoc Communications and Networks (San Diego, CA, June 18–21, 2007), IEEE, Piscataway, NJ, 2007, pp. 152–161.
• Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs, P. Kaski, A. Penttinen, and J. Suomela, Proc. 6th International Conference on Ad-Hoc Networks & Wireless (Morelia, Mexico, September 24–26, 2007), Lecture Notes in Computer Science, Vol. 4686, Springer-Verlag, Berlin Heidelberg, 2007, pp. 74–86.
• Local approximation algorithms for scheduling problems in sensor networks, P. Floréen, P. Kaski, T. Musto, and J. Suomela, Proceedings of the 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors, Wrocław, July 2007), Lecture Notes in Computer Science 4837, Springer-Verlag, Berlin, 2008, pp. 99–113.
• Trimmed Moebius inversion and graphs of bounded degree, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (Bordeaux, February 21–23, 2008) (S. Albers and P. Weil, Eds.), IBFI Schloss Dagstuhl, Wadern, Germany, 2008, pp. 85–96.
• Approximating max-min linear programs with local algorithms, P. Floréen, P. Kaski, T. Musto, and J. Suomela, Proceedings of the 2008 IEEE International Parallel and Distributed Processing Symposium (Miami, FL, USA, April 14–18, 2008), IEEE, 2008, 10 pp.
• The travelling salesman problem in bounded degree graphs, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 35th International Colloquium on Automata, Languages and Programming (Reykjavík, July 7–11, 2008), Part I, Lecture Notes in Computer Science 5125, Springer-Verlag, Berlin, 2008, pp. 198–209.
• Tight local approximation results for max-min linear programs, P. Floréen, M. Hassinen, P. Kaski, and J. Suomela, Algorithmic Aspects of Wireless Sensor Networks, Fourth International Workshop, ALGOSENSORS 2008 (Reykjavík, July 12, 2008), Lecture Notes in Computer Science 5389, Springer-Verlag, Berlin, 2008, pp. 2–17.
• Computing the Tutte polynomial in vertex-exponential time, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008, Philadelphia, PA, October 25–28, 2008), IEEE Computer Society, Los Alamitos, CA, 2008, pp. 677–686.
• An optimal local approximation algorithm for max-min linear programs, P. Floréen, J. Kaasinen, P. Kaski, and J. Suomela, Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2009 (Calgary, August 11–13), to appear.
• Counting paths and packings in halves, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009 (Copenhagen, September 7–9), to appear.

Doctoral dissertation

• Algorithms for classification of combinatorial objects, P. Kaski, Research Report A94, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2005.

Unrefereed reports

• A census of Steiner triple systems and some related combinatorial objects, P. Kaski, Research Report A78, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, June 2003. (Reprint of Licentiate's thesis.)
• Isomorph-free exhaustive generation of combinatorial designs, P. Kaski, Research Report A70, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, December 2001. (Reprint of Master's thesis.)
• libexact User's Guide, Version 1.0, P. Kaski and O. Pottonen, HIIT Technical Reports 2008–1, Helsinki Institute for Information Technology HIIT, 2008.

Manuscripts submitted for publication

• Barriers and local minima in energy landscapes of stochastic local search, P. Kaski.
• The fast intersection transform with applications to counting paths, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto.
• On evaluation of permanents, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto.
• The number of Latin squares of order 11, A. Hulpke, P. Kaski, P. R. J. Östergård.

Software

• libexact, a software library for solving combinatorial exact covering problems.