Affiliations

Our research team is affiliated with two institutions:

• Helsinki Institute for Information Technology HIIT
• Department of Computer Science, University of Helsinki

We are part of the New Paradigms in Computing research group at HIIT.

Research

Our current research focuses on the foundations of distributed computing, in particular:

• deterministic distributed algorithms
• local algorithms (constant-time distributed algorithms)
• algorithms in anonymous networks

The key research question is related to the concept of locality in the context large computer networks. There are many computational tasks that are of a global nature: to solve such a task, it is necessary to transfer information over a long distance, from one side of the network to another. However, there are also tasks that are of a local nature: it is sufficient for each network device to gather information from its own local neighbourhood. Our research team conducts basic research that aims at understanding which computational tasks are local and which are global.

Team Members

Current team members:

• Jukka Suomela, PI
• Juho Hirvonen, PhD student
• Joel Rybicki, PhD student
• Tuomo Lempiäinen, research assistant

Former team members:

• Matti Åstrand – University of Pennsylvania
• Mika Göös – University of Toronto
• Jara Uitto – ETH Zurich
• Marja Hölttä
• Joel Kaasinen
• Juhana Laurinharju
• Topi Musto

News

2013

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

2012

• Interview by Abstract Talk
• Best paper award at DISC 2012: “No sublogarithmic-time approximation scheme for bipartite vertex cover”
• Best student paper award at PODC 2012: “Lower bounds for local approximation”
• The Finnish Society for Computer Science granted the annual Master's thesis award 2010–2011 to Joel Rybicki

2011

• Tutorial on local algorithms at the MITACS Workshop on Wireless Networks and Mobile Computing in Ottawa

Publications

2013

• Jukka Suomela: Survey of local algorithms, ACM Computing Surveys

2012

• Mika Göös and Jukka Suomela: No sublogarithmic-time approximation scheme for bipartite vertex cover, DISC 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
• Mika Göös, Juho Hirvonen, and Jukka Suomela: Lower bounds for local approximation, 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

2011

• 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
• 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
• Evangelos Kranakis, Oscar Morales Ponce, and Jukka Suomela: Planar subgraphs without low-degree nodes, WADS 2011
• Mika Göös and Jukka Suomela: Locally checkable proofs, PODC 2011

2010

• Jukka Suomela: Paikallinen laskettavuus, Tietojenkäsittelytiede
• Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela: Almost stable matchings by truncating the Gale–Shapley algorithm, Algorithmica
• Jukka Suomela: Distributed algorithms for edge dominating sets, PODC 2010
• Matti Åstrand and Jukka Suomela: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks, SPAA 2010

2009

• Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer: Local algorithms: self-stabilization on speed, SSS 2009
• Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto: A local 2-approximation algorithm for the vertex cover problem, DISC 2009
• Patrik Floréen, Joel Kaasinen, Petteri Kaski, and Jukka Suomela: An optimal local approximation algorithm for max-min linear programs, SPAA 2009
• Valentin Polishchuk and Jukka Suomela: A simple local 3-approximation algorithm for vertex cover, Information Processing Letters

2008

• Petteri Kaski, Aleksi Penttinen, and Jukka Suomela: Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs, Ad Hoc & Sensor Wireless Networks
• Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela: Improved approximation algorithms for relay placement, ESA 2008
• Valentin Polishchuk and Jukka Suomela: Optimal backlog in the plane, Algosensors 2008
• Patrik Floréen, Marja Hassinen, Petteri Kaski, and Jukka Suomela: Tight local approximation results for max-min linear programs, Algosensors 2008
• Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela: Approximating max-min linear programs with local algorithms, IPDPS 2008
• Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela: Local approximation algorithms for scheduling problems in sensor networks, Algosensors 2007

2007

• Petteri Kaski, Aleksi Penttinen, and Jukka Suomela: Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs, AdHoc-NOW 2007
• Jukka Suomela: Approximability of identifying codes and locating-dominating codes, Information Processing Letters
• Patrik Floréen, Petteri Kaski, and Jukka Suomela: A distributed approximation scheme for sleep scheduling in sensor networks, SECON 2007

Teaching

• Autumn 2012: Seminar: Distributed Algorithms
• Spring 2012: Deterministic distributed algorithms
• Spring 2010: Deterministic distributed algorithms
• Autumn 2009: Seminar: Distributed Algorithms (in Finnish)

Acknowledgements

The research team has been supported by:

• The Academy of Finland, Grant 252018, PAIKKA project, 2011–2014, PI: Jukka Suomela
• The Research Funds of the University of Helsinki, PALA project, 2011–2013, PI: Jukka Suomela
• The Academy of Finland, Grant 132380, PAHA project, 2010–2012, PI: Patrik Floréen
• The Academy of Finland, Grant 116547, Geru project, 2007–2009, PI: Patrik Floréen
• Helsinki Graduate School in Computer Science and Engineering (Hecse)
• The Finnish Cultural Foundation
• The Foundation of Nokia Corporation

This page was last updated in March 2013.