New Paradigms in Computing

Group members: Dr. Petteri Kaski, Dr. Mikko Koivisto, Dr. Valentin Polishchuk, Dr. Jukka Suomela.

PhD students: Juho Hirvonen, Janne Korhonen, Pekka Parviainen, Joel Rybicki.

MSc students and summer interns: Sylvester Eriksson-Bique, Juha-Antti Isojärvi, Juhana Laurinharju, Tuomo Lempiäinen, Mikko Nikkilä, Mikko Sysikaski.

Former students and summer interns: Mika Göös, Topi Musto, Anne Pääkkö.

The group is a part of Helsinki Institute for Information Technology HIIT – a joint research institute of Aalto University and the University of Helsinki. We are affiliated with the ICS Department at Aalto and the CS Department at UH.

Highlights

	Extension of classical network flow results to geometric domains: we formulated and proved continuous versions of the Flow Decomposition Theorem and the Menger's Theorem; we applied the results to real-world problems arising in the air traffic industry (video).
	The Tutte polynomial of an undirected graph is one of the fundamental invariants in algebraic graph theory, with connections to graph coloring, nowhere-zero flows, network reliability, knot theory, and the Ising and Potts models in statistical physics among others. The classical algorithm for computing the Tutte polynomial proceeds by means of a deletion–contraction recurrence over the edges. We developed a new algorithm (see here for an implementation) for computing the Tutte polynomial that runs in time proportional to the number of connected vertex sets in the input graph. For example, this is currently the fastest known algorithm for graph coloring.
	The vertex cover problem is a classical NP-hard optimisation problem – in a centralised setting, there is a simple 2-approximation algorithm, and no polynomial-time algorithm with approximation factor 1.999 is known. We have studied the approximability of the vertex cover problem in a very limited model of distributed computing. We have shown that even in anonymous networks, it is possible to find a 2-approximation of vertex cover by using a deterministic algorithm. In graphs with maximum degree Δ, the running time of our algorithm is O(Δ) rounds, independent of the number of nodes.
	Our work on locally checkable proofs studies decision problems from the perspective of nondeterministic distributed algorithms: for a yes-instance there must exist a proof that can be verified with a local algorithm, all nodes must accept a valid proof, and at least one node must reject an invalid proof. We classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof, and we show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node.
	Algebras derived from a multiplicative base structure such as a group or a semigroup are the foundation of many computational applications. For example, the group algebra of a finite Abelian group, together with a fast algorithm for transforming between the elementary basis and a basis of orthogonal idempotents (that is, a fast Fourier transform, or FFT), is the foundation of efficient filtering in digital signal processing. Our work on fast zeta and Möbius transforms establishes that FFT-like algorithms exist for the semigroup algebras of finite lattices, where the depth of the FFT-circuit is controlled by the number of nonzero join-irreducible elements in the lattice.
	Localization, clustering, and activity scheduling are fundamental problems in wireless sensor networks. We developed a combined approach to the three problems, applying the “Occam’s razor principle” to data collected by the sensors; both centralised and distributed settings were considered.

News

2013

• We will organise ADGA 2013, Workshop on Advances on Distributed Graph Algorithms, as a satellite workshop of DISC 2013 in Jerusalem.

2012

• Jukka Suomela was interviewed by Abstract Talk.
• Our work “No sublogarithmic-time approximation scheme for bipartite vertex cover” received the best paper award at DISC 2012.
• Mika Göös received the best student paper award at PODC 2012 for the paper “Lower bounds for local approximation”.
• SWAT 2012 was held in Helsinki.
• The Finnish Society for Computer Science granted the annual Master's thesis award 2010–2011 to Joel Rybicki.
• Jesper Nederlof visited us on May 14–25.
• Petteri Kaski gave an invited talk on enumeration of designs with subdesigns at the 3rd Colloquium on Galois Geometry at Universiteit Gent, Belgium.

2011

• Jukka Suomela visited the Weizmann Institute of Science in November 2011 and gave a talk on distributed algorithms for maximal matchings.
• Jukka Suomela visited the Hebrew University of Jerusalem in November 2011 and gave a talk on local algorithms.
• Jesper Nederlof visited us in April–June 2011.
• Petteri Kaski received the 2011 Young Researcher Prize from the Finnish Foundation for Technology Promotion.
• Petteri Kaski gave an invited talk on cycle switching in triple systems at the 2011 International Conference on Design of Experiments in Memphis TN.
• Jukka Suomela gave a tutorial on local algorithms at the MITACS Workshop on Wireless Networks and Mobile Computing in Ottawa.
• Valentin Polishchuk visited Max-Planck-Institut für Informatik in January–February 2011.

2010

• Please see here for a new software package for computing the Tutte polynomial of a given graph.
• Jukka Suomela visited TU Braunschweig in October–December 2010 and gave talks on covering graphs, edge dominating sets, and vertex covers.
• Petteri Kaski visited Monash University and the Australian National University in November–December 2010.
• Petteri Kaski gave an invited talk at the 34th Australasian Conference on Combinatorial Mathematics & Combinatorial Computing (Australian National University, Canberra, 6–10 December 2010) on constructive and nonconstructive enumeration of designs.
• Petteri Kaski and Patric Östergård organized a minisymposium on Design Theory (including a contributed talk) at the SIAM Conference on Discrete Mathematics 2010.
• Jukka Suomela visited Carleton University in April 2010 and gave a talk on stable matchings.
• Jukka Suomela visited ETH Zurich in March 2010 and gave talks on vertex covers and stable matchings.

Mission

We perform basic research at the intersection of core computer science (algorithm design and analysis) and discrete mathematics, with an emphasis towards novel techniques and less studied models of computation.

We invest substantial effort to high-risk, high-yield research problems of relatively broad theoretical interest, selected on both problem and method driven basis. However, we also aim at rapid publication of more specific, smaller observations. We particularly seek and value solid results with mathematical elegance and simplicity.

Current research themes

1. Exploring the interplay between algebraic, combinatorial, and geometric techniques in the design of exact deterministic algorithms. For example, many combinatorial problems can be cast in algebraic form, whereby a nontrivial algebraic algorithm yields a more efficient solution compared with direct combinatorial tools.
2. Restricted models of computation and tradeoffs in resources and/or objectives. For example, one fundamental limitation in modern large-scale distributed systems is the infeasibility of central control. In practice, the system must be operated by a distributed algorithm in which each computational node operates based on the information available in its local neighbourhood only. Assuming this setting, is it possible to achieve globally optimal or near-optimal operation? What is the tradeoff between the available information and the degree of approximation for the optimum?
3. While we are a theory group, we occasionally engage in practical algorithm implementation. Examples include attacks on combinatorial classification problems and applications in computational geometry (e.g. air traffic management).

Publications

2013

• Jukka Suomela. Survey of local algorithms. ACM Computing Surveys 45 (2013), article 24.

2012

• Mika Göös and Jukka Suomela. No sublogarithmic-time approximation scheme for bipartite vertex cover. DISC 2012.
• Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. PODC 2012.
• Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema. Weak models of distributed computing, with connections to modal logic. PODC 2012.
• Juho Hirvonen and Jukka Suomela. Distributed maximal matching: greedy is optimal. PODC 2012.
• Henning Hasemann, Juho Hirvonen, Joel Rybicki, and Jukka Suomela. Deterministic local algorithms, unique identifiers, and fractional graph colouring. SIROCCO 2012.
• Matti Järvisalo, Petteri Kaski, Mikko Koivisto, Janne H. Korhonen. Finding efficient circuits for ensemble computation. SAT 2012.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, Pekka Parviainen. Fast zeta transforms for lattices with few irreducibles. SODA 2012.
• Irina Kostitsyna and Valentin Polishchuk. Simple wriggling is hard unless you are a fat hippo. To appear in Theory of Computing Systems.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The Travelling Salesman Problem in bounded degree graphs. To appear in ACM Transactions on Algorithms.
• S. Yang, J. S. B. Mitchell, J. Krozel, V. Polishchuk, J. Kim, and J. Zou. Flexible airlane generation to maximize flow under hard and soft constraints. To appear in Air Traffic Control Quarterly.
• Petteri Kaski, Mahdad Khatirinejad, and Patric R. J. Östergård. Steiner triple systems satisfying the 4-vertex condition. Designs, Codes and Cryptography 62 (2012) 323–330.

2011

• Pekka Parviainen and Mikko Koivisto. Ancestor relations in the presence of unobserved variables. ECML PKDD 2011.
• Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S. B. Mitchell, Valentin Polishchuk, Lena Schlipf, and Shang Yang. Convex transversals. WADS 2011.
• Valentin Polishchuk and Mikko Sysikaski. Faster algorithms for minimum-link paths with restricted orientations. WADS 2011.
• Evangelos Kranakis, Oscar Morales Ponce, and Jukka Suomela. Planar subgraphs without low-degree nodes. WADS 2011.
• Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto. Partial order MCMC for structure discovery in Bayesian networks. UAI 2011.
• Mika Göös and Jukka Suomela. Locally checkable proofs. PODC 2011.
• P. Agarwal, A. Efrat, C. Gniady, J. S. B. Mitchell, V. Polishchuk, and G. Sabhnani. Distributed localization and clustering using data correlation and the Occam's razor principle. DCOSS 2011.
• Tommi Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical labeling. TAPAS 2011.
• Esa Junttila and Petteri Kaski. Segmented nestedness in binary data. SIAM Data Mining 2011.
• Niko Vuokko and Petteri Kaski. Significance of patterns in time series collections. SIAM Data Mining 2011.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Covering and packing in linear space. Information Processing Letters 111 (2011) 1033–1036.
• Charles J. Colbourn, Petteri Kaski, Patric R. J. Östergård, David A. Pike, and Olli Pottonen. Nearly Kirkman triple systems of order 19 and Hanani triple systems of order 19. Discrete Mathematics 311 (2011) 827–834.
• Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela. Local approximability of max-min and min-max linear programs. Theory of Computing Systems 49 (2011) 672–697.
• Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, and Andreas Wiese. Analysing local algorithms in location-aware quasi unit-disk graphs. Discrete Applied Mathematics 159 (2011) 1566–1580.
• Petteri Kaski, Veli Mäkinen, and Patric R. J. Östergård. The cycle switching graph of the Steiner triple systems of order 19 is connected. Graphs and Combinatorics 27 (2011) 539–546.
• E. M. Arkin, M. A. Bender, J. S. B. Mitchell, and V. Polishchuk. The snowblower problem. Computational Geometry: Theory and Applications 44 (2011) 370–384.
• Alexander Hulpke, Petteri Kaski, and Patric R. J. Östergård. The number of Latin squares of order 11. Mathematics of Computation 80 (2011) 1197–1219.

2010

• Niko Vuokko and Petteri Kaski. Testing the significance of patterns in data with cluster structure. ICDM 2010.
• Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski. Dynamic one-sided boundary labeling. GIS 2010.
• Valentin Polishchuk and Arto Vihavainen. Periodic multi-labeling of public transit lines. GIScience 2010.
• Tommi Junttila and Petteri Kaski. Exact cover via satisfiability: an empirical study. CP 2010.
• Jukka Suomela. Distributed algorithms for edge dominating sets. PODC 2010.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Covering and packing in linear space. ICALP 2010.
• Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. SPAA 2010.
• Pekka Parviainen and Mikko Koivisto. Bayesian structure discovery in Bayesian networks with less space. AISTATS 2010.
• Mikko Koivisto and Pekka Parviainen. A space-time tradeoff for permutation problems. SODA 2010.
• Charles J. Colbourn, Anthony D. Forbes, Mike J. Grannell, Terry S. Griggs, Petteri Kaski, Patric R. J. Östergård, David A. Pike, and Olli Pottonen. Properties of the Steiner triple systems of order 19. Electronic Journal of Combinatorics 17 (2010) #R98, 30 pp.
• Esther Arkin, Joseph S. B. Mitchell, and Valentin Polishchuk. Maximum thick paths in static and dynamic environments. Computational Geometry: Theory and Applications 43 (2010) 279–294.
• Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Evaluation of permanents in rings and semirings. Information Processing Letters 110 (2010) 867–870.
• Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Almost stable matchings by truncating the Gale–Shapley algorithm. Algorithmica 58 (2010) 102–118.
• Jukka Suomela. Paikallinen laskettavuus. Tietojenkäsittelytiede 31 (2010) 57–69.

Software

• tutte_bhkk – a software package for computing the Tutte polynomial of a given graph (joint work with Andreas Björklund and Thore Husfeldt).
• Maplab – an automated system for labeling mass transit routes.
• bliss – a tool for computing automorphism groups and canonical labelings of graphs (joint work with Tommi Junttila).
• libexact – a software library for solving combinatorial exact covering problems (joint work with Olli Pottonen).

Teaching

• Autumn 2012: Seminar: Distributed Algorithms.
• Spring 2012: Deterministic distributed algorithms.
• Autumn 2011: Principles of algorithmic techniques.
• Spring 2011: Combinatorics.
• Autumn 2010: Computational genotype analysis.
• Autumn 2010: Design and analysis of algorithms.
• Spring 2010: Deterministic distributed algorithms.
• Spring 2010: Selected topics in complexity theory.
• Spring 2010: An introductory lecture (in Finnish) on computational complexity and NP-completeness.
• Autumn 2009: Seminar course on distributed algorithms (in Finnish).
• Spring 2009: 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: Special topics in computational geometry.

Projects

• PAIKKA project is funded by the Academy of Finland during the years 2011–2014. The project aims at opening new research directions within the field of distributed computing. The research topics include local verification and locally checkable proofs, the uniform model of distributed computing, and the concrete complexity of distributed algorithms.
• PALA project is supported by the Research Funds of the University of Helsinki during the year 2011–2013. The project explores the connections between local algorithms and other fields of computer science and mathematics.
• ASAG project aims at developing computational-geometry techniques with applications in motion planning and coordination, GIS, shape approximation and sensor networks. The funding is provided by the Academy of Finland during the years 2011–2013.
• COALESCE (Combinatorial and Algebraic Representations in Algorithm Design and Complexity) project carries out basic research at the intersection of algorithm design, discrete mathematics, and theoretical computer science. On one hand the objective is to develop combinatorial and algebraic tools to attack specific computational problems (both in theory and in practice, the latter in particular as pertains to combinatorial classication and analysis), on the other hand to develop the underlying theory and advance the combinatorial/algebraic paradigm in algorithmics. The project is funded by the Academy of Finland during the years 2011–2016.
• PAHA project explores the capabilities and inherent limitations of local distributed algorithms. The research project is funded by the Academy of Finland during the years 2010–2012, and it continues the work initiated in the Academy of Finland project Optimising data gathering in resource-constrained networks (Geru, 2007–2009).
• Algorithmics in data analysis: basic research and applications (ADA-BRA) is an Academy Research Fellow project (2008–2013) funded by the Academy of Finland. The project formulates and studies computational problems motivated by established probabilistic models, with applications to data analysis, particularly in bioinformatics.