Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Lempiäinen, Tuomo"'
Autor:
Balliu, Alkida, Hirvonen, Juho, Korhonen, Janne H., Lempiäinen, Tuomo, Olivetti, Dennis, Suomela, Jukka
A number of recent papers -- e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) -- have advanced our understanding of one of the most fundamental questions in
Externí odkaz:
http://arxiv.org/abs/1711.01871
Autor:
Lempiäinen, Tuomo, Suomela, Jukka
While the relationship of time and space is an established topic in traditional centralised complexity theory, this is not the case in distributed computing. We aim to remedy this by studying the time and space complexity of algorithms in a weak mess
Externí odkaz:
http://arxiv.org/abs/1705.03876
Autor:
Brandt, Sebastian, Hirvonen, Juho, Korhonen, Janne H., Lempiäinen, Tuomo, Östergård, Patric R. J., Purcell, Christopher, Rybicki, Joel, Suomela, Jukka, Uznański, Przemysław
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of
Externí odkaz:
http://arxiv.org/abs/1702.05456
Autor:
Brandt, Sebastian, Fischer, Orr, Hirvonen, Juho, Keller, Barbara, Lempiäinen, Tuomo, Rybicki, Joel, Suomela, Jukka, Uitto, Jara
We show that any randomised Monte Carlo distributed algorithm for the Lov\'asz local lemma requires $\Omega(\log \log n)$ communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special ca
Externí odkaz:
http://arxiv.org/abs/1511.00900
Autor:
Lempiäinen, Tuomo
Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different models of distributed computing - one of which is the port-numbering model - and provided a complete classification of their computational power relative to each other. H
Externí odkaz:
http://arxiv.org/abs/1505.02322
Publikováno v:
J. Comput. Syst. Sci. 80 (2014) 297-319
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular col
Externí odkaz:
http://arxiv.org/abs/1412.7219
Autor:
Hella, Lauri, Järvisalo, Matti, Kuusisto, Antti, Laurinharju, Juhana, Lempiäinen, Tuomo, Luosto, Kerkko, Suomela, Jukka, Virtema, Jonni
This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering mo
Externí odkaz:
http://arxiv.org/abs/1205.2051
Autor:
Lempiäinen, Tuomo
Publikováno v:
Proceedings of the 2015 30th Annual ACM,IEEE Symposium on Logic in Computer Science; 7/5/2016, p357-366, 10p
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.