Petteri Kaski

Academy Research Fellow, Docent, D.Sc.(Tech.)

Mailing address:

Aalto University, School of Science
Department of Information and Computer Science
P.O. Box 15400, FI-00076 Aalto, Finland

Office:

Computer Science Building, Room B354
Aalto University, School of Science
Konemiehentie 2, FI-02150 Espoo, Finland

Office hours:

By appointment

Email:

petteri.kaski(at)aalto.fi

Telephone:

+358 9 470 23260 (office), +358 9 470 23369 (fax)

SWAT 2012

13th Scandinavian Symposium and Workshops on Algorithm Theory, Helsinki, Finland, 4–6 July 2012

Research Group

Together with Mikko Koivisto, Valentin Polishchuk, and Jukka Suomela, we form the research group New Paradigms in Computing at Helsinki Institute for Information Technology HIIT.

Teaching

• Autumn 2011: T-79.4202 Principles of Algorithmic Techniques.
• Spring 2011: T-79.5205 Combinatorics.
• Autumn 2010: T-79.4202 Principles of Algorithmic Techniques (3 contributed lectures).
• Spring 2010: An introductory lecture (in Finnish) on computational complexity and NP-completeness.
• Spring 2010: T-79.7003 Selected topics in complexity theory.
• 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: 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 7 (2010) 163–176. (Associated discussion paper appears in Biogeosciences Discussion 6 (2009) 7053–7081.)
• Almost stable matchings by truncating the Gale–Shapley algorithm, P. Floréen, P. Kaski, V. Polishchuk, and J. Suomela, Algorithmica 58 (2010) 102–118.
• Evaluation of permanents in rings and semirings, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Information Processing Letters 110 (2010) 867–870.
• Trimmed Moebius inversion and graphs of bounded degree, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Theory of Computing Systems 47 (2010) 637–654.
• Properties of the Steiner triple systems of order 19, C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike, and O. Pottonen, Electronic Journal of Combinatorics 17(1) (2010) #R98, 30 pp.
• The number of Latin squares of order 11, A. Hulpke, P. Kaski, and P. R. J. Östergård, Mathematics of Computation 80 (2011) 1197–1219.
• The cycle switching graph of the Steiner triple systems of order 19 is connected, P. Kaski, V. Mäkinen, and P. R. J. Östergård, Graphs and Combinatorics 27 (2011) 539–546.
• Local approximability of max-min and min-max linear programs, P. Floréen, M. Hassinen, J. Kaasinen, P. Kaski, T. Musto, and J. Suomela, Theory of Computing Systems 49 (2011) 672–697.
• Covering and packing in linear space, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Information Processing Letters 111 (2011) 1033–1036.
• Nearly Kirkman triple systems of order 19 and Hanani triple systems of order 19, C. J. Colbourn, P. Kaski, P. R. J. Östergård, D. A. Pike, and O. Pottonen, Discrete Mathematics 311 (2011) 827–834.
• Steiner triple systems satisfying the 4-vertex condition, P. Kaski, M. Khatirinejad, and P. R. J. Östergård, Designs, Codes and Cryptography 62 (2012) 323–330.
• The travelling salesman problem in bounded degree graphs, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, ACM Transactions on Algorithms, 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), ACM, 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), ACM, New York, 2009, pp. 260–269.
• Counting paths and packings in halves, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Algorithms - ESA 2009, 17th Annual European Symposium (Copenhagen, Denmark, September 7–9, 2009), Lecture Notes in Computer Science 5757, Springer-Verlag, Berlin, 2009, pp. 578–586.
• Covering and packing in linear space, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (Bordeaux, July 6–10, 2010), Part I, Lecture Notes in Computer Science 6198, Springer-Verlag, Berlin, 2010, pp. 727–737.
• Exact cover via satisfiability: an empirical study, T. Junttila and P. Kaski, Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming 2010 (CP 2010, St. Andrews, Scotland, September 6–10), Lecture Notes in Computer Science 6308, Springer-Verlag, Berlin, 2010, pp. 297–304.
• Testing the significance of patterns in data with cluster structure, N. Vuokko and P. Kaski, Proceedings of the 10th IEEE International Conference on Data Mining (ICDM2010, Sydney, December 14–17), IEEE Computer Society, Los Alamitos, CA, 2010, pp. 1097–1102.
• Conflict propagation and component recursion for canonical labeling, T. Junttila and P. Kaski, Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in Computer Systems (TAPAS 2011, Rome, 18–20 April 2011), Lecture Notes in Computer Science 6595, Springer-Verlag, Berlin, 2011, pp. 151–162.
• Segmented nestedness in binary data, E. Junttila and P. Kaski, Proceedings of the Eleventh SIAM International Conference on Data Mining (Mesa, AZ, 28–30 April, 2011), SIAM, Philadelphia, PA, 2011, pp. 235–246.
• Significance of patterns in time series collections, N. Vuokko and P. Kaski, Proceedings of the Eleventh SIAM International Conference on Data Mining (Mesa, AZ, 28–30 April, 2011), SIAM, Philadelphia, PA, 2011, pp. 676–686.
• Fast zeta transforms for lattices with few irreducibles, A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, J. Nederlof, and P. Parviainen, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012, Kyoto, 17–19 January, 2012), SIAM, Philadelphia, PA, 2012, pp. 1436–1444.
• Finding efficient circuits for ensemble computation, M. Järvisalo, P. Kaski, M. Koivisto, and J. H. Korhonen, Proceedings of the Fifteenth International Conference on Theory and Applications of Satisfiability Testing (SAT 2012, Trento, 17–20 June, 2012), 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

• Narrow sieves for parameterized paths and packings, A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto.

Software

• tutte_bhkk, a software package for computing the Tutte polynomial of a given graph.
• libexact, a software library for solving combinatorial exact covering problems.