Filter
Conference contribution

Search results

  • 2022

    Brief Announcement: Temporal Locality in Online Algorithms

    Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J. & Tereshchenko, A., 1 Oct 2022, 36th International Symposium on Distributed Computing, DISC 2022. Scheideler, C. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 3 p. 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 246).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientific

    Open Access
    File
    5 Downloads (Pure)
  • Dynamic Meta-Theorems for Distance and Matching

    Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V. R. & Tewari, R., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-20 20 p. 118. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

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

    Open Access
    File
    6 Downloads (Pure)
  • Efficient Classification of Locally Checkable Problems in Regular Trees

    Balliu, A., Brandt, S., Chang, Y-J., Olivetti, D., Studený, J. & Suomela, J., 2022, 36th International Symposium on Distributed Computing (DISC 2022). Scheideler, C. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-19 8. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 246).

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

    Open Access
    File
    6 Downloads (Pure)
  • Local Mending

    Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J. & Suomela, J., 2022, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Parter, M. (ed.). p. 1-20 20 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13298 LNCS).

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

    Open Access
  • On the Price of Locality in Static Fast Rerouting

    Foerster, K. T., Hirvonen, J., Pignolet, Y. A., Schmid, S. & Tredan, G., 2022, Proceedings - 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2022. IEEE, p. 215-226 12 p.

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

    Open Access
    1 Citation (Scopus)
  • Sparse Matrix Multiplication in the Low-Bandwidth Model

    Gupta, C., Hirvonen, J., Korhonen, J. H., Studený, J. & Suomela, J., 11 Jul 2022, SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, p. 435-444 10 p.

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

    Open Access
    File
    23 Downloads (Pure)
  • 2021

    Brief announcement: Sinkless orientation is hard also in the supported LOCAL model

    Korhonen, J. H., Paz, A., Rybicki, J., Schmid, S. & Suomela, J., 1 Oct 2021, 35th International Symposium on Distributed Computing, DISC 2021. Gilbert, S. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 4 p. 58. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 209).

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

    Open Access
    File
    7 Downloads (Pure)
  • Distributed Graph Problems Through an Automata-Theoretic Lens

    Chang, Y-J., Studený, J. & Suomela, J., 28 Jun 2021, Structural Information and Communication Complexity: 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 – July 1, 2021, Proceedings. Jurdziński, T. & Schmid, S. (eds.). 31 p. (Lecture Notes in Computer Science; vol. 12810).

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

    Open Access
    File
    6 Citations (Scopus)
    7 Downloads (Pure)
  • Efficient load-balancing through distributed token dropping

    Brandt, S., Keller, B., Rybicki, J., Suomela, J. & Uitto, J., 6 Jul 2021, SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. ACM, p. 129-139 11 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

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

    Open Access
    1 Citation (Scopus)
  • Locally checkable labelings with small messages

    Balliu, A., Censor-Hillel, K., Maus, Y., Olivetti, D. & Suomela, J., 2021, 35th International Symposium on Distributed Computing, DISC 2021. Gilbert, S. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 18 p. 8. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 209).

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

    Open Access
    File
    5 Citations (Scopus)
    11 Downloads (Pure)
  • On the Feasibility of Perfect Resilience with Local Fast Failover

    Foerster, K. T., Hirvonen, J., Pignolet, Y-A., Schmid, S. & Tredan, G., 2021, Proceedings of SIAM-ACM Symposium on Algorithmic Principles of Computer Systems, APOCS 2021). SIAM, 15 p.

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

    Open Access
  • Reachability and Matching in Single Crossing Minor Free Graphs

    Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V. & Tewari, R., 29 Nov 2021, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-16 16 p. 16. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 213).

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

    Open Access
    File
    8 Downloads (Pure)
  • Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs

    Gupta, C., Jain, R. & Tewari, R., 29 Nov 2021, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-15 15 p. 23. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 213).

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

    Open Access
    File
    9 Downloads (Pure)
  • 2020

    Brief Announcement: Classification of Distributed Binary Labeling Problems

    Balliu, A., Brandt, S., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D. & Suomela, J., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. ACM, p. 349-351 3 p.

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

    Open Access
    File
    35 Downloads (Pure)
  • Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens

    Chang, Y-J., Studený, J. & Suomela, J., 7 Oct 2020, 34th International Symposium on Distributed Computing. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Vol. 179. 3 p.

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

    Open Access
    File
    15 Downloads (Pure)
  • Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

    Sebastian, B., Keller, B., Rybicki, J., Suomela, J. & Uitto, J., 2020, 34th International Symposium on Distributed Computing (DISC 2020). Attiya, H. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-3 3 p. 40. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 179).

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

    Open Access
    File
    1 Citation (Scopus)
    8 Downloads (Pure)
  • Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

    Foerster, K. T., Hirvonen, J., Pignolet, Y-A., Schmid, S. & Tredan, G., 2020, 34th International Symposium on Distributed Computing (DISC 2020). Attiya, H. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 3 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 179).

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

    Open Access
    File
    5 Downloads (Pure)
  • Classification of Distributed Binary Labeling Problems

    Balliu, A., Sebastian, B., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D. & Suomela, J., 2020, 34th International Symposium on Distributed Computing (DISC 2020). Attiya, H. (ed.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 17 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 179).

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

    Open Access
    File
    15 Downloads (Pure)
  • How much does randomness help with locally checkable problems?

    Balliu, A., Brandt, S., Olivetti, D. & Suomela, J., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. ACM, p. 299-308 10 p.

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

    Open Access
    10 Citations (Scopus)
  • Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems

    Rosenbaum, W. & Suomela, J., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. ACM, p. 89-98 10 p.

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

    Open Access
    6 Citations (Scopus)
  • 2019

    Distributed reconfiguration of maximal independent sets

    Censor-Hillel, K. & Rabie, M., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 135. (Leibniz international proceedings in informatics; vol. 132).

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

    Open Access
    File
    1 Citation (Scopus)
    49 Downloads (Pure)
  • 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
  • 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
    7 Citations (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
    7 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
    13 Citations (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 für Informatik, 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
    15 Citations (Scopus)
    48 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 für Informatik, p. 1-15 9. (OASIcs; vol. 65).

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

    Open Access
    File
    30 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-Zentrum für Informatik, p. 1-16 30. (Leibniz International Proceedings in Informatics; vol. 95).

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

    Open Access
    File
    23 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 für Informatik, 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
    7 Citations (Scopus)
    24 Downloads (Pure)
  • Local Verification of Global Proofs

    Feuilloley, L. & Hirvonen, J., 1 Oct 2018, 32nd International Symposium on Distributed Computing (DISC 2018). Schmid, U. & Hirvonen, J. (eds.). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-17 17 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 121).

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

    Open Access
    File
    9 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
    19 Citations (Scopus)
    121 Downloads (Pure)
  • Redundancy in Distributed Proofs

    Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A. & Perry, M., 1 Oct 2018, 32nd International Symposium on Distributed Computing (DISC 2018). Schmid, U. & Hirvonen, J. (eds.). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, p. 1-18 18 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 121).

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

    Open Access
    File
    36 Downloads (Pure)
  • 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
    15 Citations (Scopus)
  • 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 für Informatik, p. 1-3 55. (Leibniz International Proceedings in Informatics; vol. 91).

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

    Open Access
    File
    5 Citations (Scopus)
    27 Downloads (Pure)
  • Deterministic Subgraph Detection in Broadcast CONGEST

    Korhonen, J. H. & Rybicki, J., 2017, 21st International Conference on Principles of Distributed Systems, OPODIS 2017. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 4. (Leibniz International Proceedings in Informatics; vol. 95).

    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., 2017, 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 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
    11 Citations (Scopus)
    159 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

    35 Citations (Scopus)
  • 2016

    Ability to count messages is worth Θ(Δ) rounds in distributed computing

    Lempiäinen, T., 5 Jul 2016, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. New York, NY, USA: ACM, p. 357-366 (Annual ACM/IEEE Symposium on Logic in Computer Science).

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

  • A Hierarchy of Local Decision

    Feuilloley, L., Fraigniaud, P. & Hirvonen, J., 2016, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Ioannis Chatzigiannakis Michael Mitzenmacher, Y. R. & Sangiorgi, D. (eds.). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Vol. 55. p. 1-15 118. (Leibniz International Proceedings in Informatics (LIPIcs)).

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

    Open Access
    File
    20 Citations (Scopus)
    43 Downloads (Pure)
  • 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

    87 Citations (Scopus)
  • Near-optimal self-stabilising counting and firing squads

    Lenzen, C. & Rybicki, J., 2016, Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Proceedings. Vol. 10083 LNCS. p. 263-280 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10083 LNCS).

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

    7 Citations (Scopus)
  • 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, 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

    10 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 für 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
    33 Downloads (Pure)