• Aalto SCI Computer Science Konemiehentie 2

20072020

Research output per year

If you made any changes in Pure these will be visible here soon.

Research Output

2019

33rd International Symposium on Distributed Computing, DISC 2019, October 14–18, 2019, Budapest, Hungary

Suomela, J. (ed.), 2019, (Leibniz International Proceedings in Informatics; vol. 146)

Research output: Book/ReportAnthologyScientificpeer-review

Open Access

Algebraic methods in the congested clique

Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. & Suomela, J., 2019, In : DISTRIBUTED COMPUTING. 32, 6, p. 461-478 18 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Hardness of Minimal Symmetry Breaking in Distributed Computing

Balliu, A., Hirvonen, J., Olivetti, D. & Suomela, J., 2019, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019). ACM, p. 369-378

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access

Improved distributed degree splitting and edge coloring

Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y., Suomela, J. & Uitto, J., 4 Feb 2019, In : DISTRIBUTED COMPUTING. 18 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Locality of not-so-weak coloring

Balliu, A., Hirvonen, J., Lenzen, C., Olivetti, D. & Suomela, J., 2019, Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, Proceedings. p. 37-51 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in ; vol. 11639 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
1 Citation (Scopus)

Lower bounds for maximal matchings and maximal independent sets

Balliu, A., Sebastian, B., Hirvonen, J., Olivetti, D., Rabie, M. & Suomela, J., 2019, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access

On the Power of Preprocessing in Decentralized Network Optimization

Foerster, K. T., Hirvonen, J., Schmid, S. & Suomela, J., 1 Apr 2019, INFOCOM 2019 - IEEE Conference on Computer Communications. IEEE, p. 1450-1458 9 p. 8737382. (Proceedings - IEEE INFOCOM; vol. 2019-April).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
2 Citations (Scopus)

The distributed complexity of locally checkable problems on paths is decidable

Balliu, A., Brandt, S., Chang, Y. J., Olivetti, D., Rabie, M. & Suomela, J., 16 Jul 2019, PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM, p. 262-271 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
1 Citation (Scopus)
2018

Almost global problems in the LOCAL model

Balliu, A., Brandt, S., Olivetti, D. & Suomela, J., 2018, 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 121. p. 1-16 9. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 121).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
7 Citations (Scopus)
8 Downloads (Pure)

Changing lanes on a highway

Petig, T., Schiller, E. M. & Suomela, J., 1 Aug 2018, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-15 9. (OASIcs; vol. 65).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
13 Downloads (Pure)

Constant space and non-constant time in distributed computing

Lempiäinen, T. & Suomela, J., Mar 2018, 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Schloss Dagstuhl - Leibniz Center for Informatics, p. 1-16 30. (Leibniz International Proceedings in Informatics; vol. 95).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
6 Downloads (Pure)

Distributed recoloring

Bonamy, M., Ouvrard, P., Rabie, M., Suomela, J. & Uitto, J., 1 Oct 2018, 32nd International Symposium on Distributed Computing, DISC 2018. Schmid, U. & Widder, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-17 12. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 121).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
3 Citations (Scopus)
14 Downloads (Pure)

New classes of distributed time complexity

Balliu, A., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Olivetti, D. & Suomela, J., 20 Jun 2018, STOC 2018 – Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM, p. 1307-1318 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
7 Citations (Scopus)
102 Downloads (Pure)

Node labels in local decision

Fraigniaud, P., Hirvonen, J. & Suomela, J., 2018, In : Theoretical Computer Science. 751, p. 61-73

Research output: Contribution to journalArticleScientificpeer-review

Open Access

Towards a complexity theory for the congested clique

Korhonen, J. H. & Suomela, J., 2018, SPAA’18, Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures. ACM, p. 163-172 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
3 Citations (Scopus)

Variation in the productivity of adjective comparison in Present-day English

Säily, T., González-Díaz, V. & Suomela, J., 2018, Corpus Approaches to Contemporary British Speech: Sociolinguistic Studies of the Spoken BNC2014. Brezina, V., Love, R. & Aijmer, K. (eds.). Routledge, 26 p. (Routledge Advances in Corpus Linguistics; no. 21).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Open Access
File
16 Downloads (Pure)
2017

Brief announcement: Towards a complexity theory for the congested clique

Korhonen, J. H. & Suomela, J., 1 Oct 2017, 31st International Symposium on Distributed Computing, DISC 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-3 55. (Leibniz International Proceedings in Informatics; vol. 91).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
4 Citations (Scopus)
10 Downloads (Pure)

Efficient counting with optimal resilience

Lenzen, C., Rybicki, J. & Suomela, J., 2017, In : SIAM JOURNAL ON COMPUTING. 46, 4, p. 1473-1500 28 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
2 Citations (Scopus)
104 Downloads (Pure)

Improved distributed degree splitting and edge coloring

Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y., Suomela, J. & Uitto, J., 2017, 31st International Symposium on Distributed Computing (DISC 2017). p. 1-15 19. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 91).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
7 Citations (Scopus)
86 Downloads (Pure)

Large Cuts with Local Algorithms on Triangle-Free Graphs

Hirvonen, J., Rybicki, J., Schmid, S. & Suomela, J., 20 Oct 2017, In : The Electronic Journal of Combinatorics. 24, 4, p. 1-20 20 p., P4.21.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
6 Citations (Scopus)
24 Downloads (Pure)

LCL problems on grids

Brandt, S., Hirvonen, J., Korhonen, J. H., Lempiäinen, T., Östergård, P. R. J., Purcell, C., Rybicki, J., Suomela, J. & Uznański, P., 26 Jul 2017, PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, Vol. Part F129314. p. 101-110 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

16 Citations (Scopus)

Linear-in-Δ lower bounds in the LOCAL model

Göös, M., Hirvonen, J. & Suomela, J., 2017, In : DISTRIBUTED COMPUTING. 30, 5, p. 325-338

Research output: Contribution to journalArticleScientificpeer-review

4 Citations (Scopus)

types2: Exploring word-frequency differences in corpora

Säily, T. & Suomela, J., 2017, Big and Rich Data in English Corpus Linguistics, Methods and Explorations. (Studies in Variation, Contacts and Change in English; vol. 19).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

2016

A lower bound for the distributed Lovász local lemma

Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempiäinen, T., Rybicki, J., Suomela, J. & Uitto, J., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM, Vol. 19-21-June-2016. p. 479-488 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

43 Citations (Scopus)

Deterministic local algorithms, unique identifiers, and fractional graph colouring

Hasemann, H., Hirvonen, J., Rybicki, J. & Suomela, J., 11 Jan 2016, In : Theoretical Computer Science. 610, Part B, p. 204-217 14 p.

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Improved Approximation Algorithms for Relay Placement

Efrat, A., Fekete, S. P., Mitchell, J. S. B., Polishchuk, V. & Suomela, J., Feb 2016, In : ACM Transactions on Algorithms. 12, 2, 28 p., 20.

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

Locally checkable proofs in distributed computing

Göös, M. & Suomela, J., 2016, In : THEORY OF COMPUTING. 12, p. 1–33 19.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
24 Citations (Scopus)
59 Downloads (Pure)

Non-local Probes Do Not Help with Many Graph Problems

Göös, M., Hirvonen, J., Levi, R., Medina, M. & Suomela, J., 2016, Distributed Computing: 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings. Gavoille, C. & Ilcinkas, D. (eds.). Berlin, Heidelberg: Springer Berlin Heidelberg, Vol. 9888 LNCS. p. 201-214 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9888 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Citations (Scopus)

Randomized algorithms for finding a majority element

Gawrychowski, P., Suomela, J. & Uznanski, P., 2016, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 1-14 14 p. 9. (Leibniz International Proceedings in Informatics).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
19 Downloads (Pure)

Synchronous counting and computational algorithm design

Dolev, D., Heljanko, K., Järvisalo, M., Korhonen, J., Lenzen, C., Rybicki, J., Suomela, J. & Wieringa, S., 1 Mar 2016, In : JOURNAL OF COMPUTER AND SYSTEM SCIENCES. 82, 2, p. 310-332 23 p.

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)
2015

Algebraic methods in the congested clique

Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. & Suomela, J., 2015, 34th Annual ACM Symposium on Principles of Distributed Computing (PODC), Donostia-San Sebastián, Spain, July 2015. ACM, p. 143-152

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

53 Citations (Scopus)

Exact Bounds for Distributed Graph Colouring

Rybicki, J. & Suomela, J., 2015, International Colloquium on Structural Information and Communication Complexity (SIROCCO), Montserrat, Spain, July 15-17, 2015. p. 46-60

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Local coordination and symmetry breaking

Suomela, J., 2015, In : Bulletin of the EATCS. 115, p. 83-110

Research output: Contribution to journalArticleProfessional

Locally optimal load balancing

Feuilloley, L., Hirvonen, J. & Suomela, J., 2015, 29th International Symposium on Distributed Computing (DISC), Tokyo, Japan, October 5-9, 2015. p. 544-558

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Node labels in local decision

Fraigniaud, P., Hirvonen, J. & Suomela, J., 2015, Structural Information and Communication Complexity: 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015. Post-Proceedings. p. 31-45 (Lecture Notes in Computer Science; vol. 9439).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

The minimum backlog problem

Bender, M. A., Fekete, S. P., Kröller, A., Liberatore, V., Mitchell, J. S. B., Polishchuk, V. & Suomela, J., 2015, In : Theoretical Computer Science. 605, p. 51-61

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)

Towards Optimal Synchronous Counting

Lenzen, C., Rybicki, J. & Suomela, J., 2015, ACM Symposium on Principles of Distributed Computing (PODC), Donostia-San Sebastián, Spain, July 21 - 23, 2015. p. 441-450

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

7 Citations (Scopus)

Weak models of distributed computing, with connections to modal logic

Hella, L., Järvisalo, M., Kuusisto, A., Laurinharju, J., Lempiäinen, T., Luosto, K., Suomela, J. & Virtema, J., 2015, In : DISTRIBUTED COMPUTING. 28, 1, p. 31-53

Research output: Contribution to journalArticleScientificpeer-review

2014

Brief announcement: Linial's lower bound made easy

Laurinharju, J. & Suomela, J., 2014, 33rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Paris, France, July 2014. ACM, p. 377-378

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)

Brief announcement: Local approximability of minimum dominating set on planar graphs

Hilke, M., Lenzen, C. & Suomela, J., 2014, ACM Symposium on Principles of Distributed Computing, PODC, Paris, France, July 2014. ACM, p. 344-346

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Citations (Scopus)

Linear-in-Delta lower bounds in the LOCAL model

Göös, M., Hirvonen, J. & Suomela, J., 2014, ACM Symposium on Principles of Distributed Computing, PODC, Paris, France, July 2014. ACM, p. 86-95 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

No sublogarithmic-time approximation scheme for bipartite vertex cover

Göös, M. & Suomela, J., 2014, In : DISTRIBUTED COMPUTING. 27, 6, p. 435-443

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

types2: Type and Hapax Accumulation Curves

Suomela, J., 2014

Research output: Artistic and non-textual formSoftwareScientific

2010

Almost stable matchings by truncating the Gale-Shapley algorithm

Floréen, P., Kaski, P., Polishchuk, V. & Suomela, J., 2010, In : Algorithmica. 58, 1, p. 102-118

Research output: Contribution to journalArticleScientificpeer-review

25 Citations (Scopus)

Local approximability of max-min and min-max linear programs

Floréen, P., Hassinen, M., Kaasinen, J., Kaski, P., Musto, T. & Suomela, J., 2010, In : THEORY OF COMPUTING SYSTEMS. 49, 4, p. 672-697

Research output: Contribution to journalArticleScientificpeer-review

2008

Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum Weight Independent Set in Local Conflict Graphs

Kaski, P., Penttinen, A. & Suomela, J., 2008, In : Ad Hoc & Sensor Wireless Networks. 6, 3-4, p. 239-263

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
2007

Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum Weight Independent Set in Local Conflict Graphs

Kaski, P., Penttinen, A. & Suomela, J., 2007, 6th International Conference on AD-HOC Networks & Wireless, AdHoc-Now 2007, Lecture Notes in Computer Science, Morelia, Mexico, September 24-26, 2007. p. 74-86

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)