Jukka Suomela

Theor. Comput. Sci., January, 2024

Distributed Quantum Advantage for Local Problems.

[BibT_eX]

[DOI]

CoRR, 2024

Shared Randomness Helps with Local Distributed Problems.

[BibT_eX]

[DOI]

CoRR, 2024

Local Advice and Local Decompression.

[BibT_eX]

[DOI]

CoRR, 2024

Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity.

[BibT_eX]

[DOI]

CoRR, 2024

Online Locality Meets Distributed Quantum Computing.

[BibT_eX]

[DOI]

CoRR, 2024

No Distributed Quantum Advantage for Approximate Graph Coloring.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Brief Announcement: Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity.

[BibT_eX]

[DOI]

Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures, 2024

Distributed Binary Labeling Problems in High-Degree Graphs.

[BibT_eX]

[DOI]

Henrik Lievonen

Timothé Picavet

Proceedings of the Structural Information and Communication Complexity, 2024

Brief Announcement: Local Advice and Local Decompression.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Local Problems in Trees Across a Wide Range of Distributed Models.

[BibT_eX]

[DOI]

Proceedings of the 28th International Conference on Principles of Distributed Systems, 2024

2023

Locally checkable problems in rooted trees.

[BibT_eX]

[DOI]

Distributed Comput., September, 2023

Distributed graph problems through an automata-theoretic lens.

[BibT_eX]

[DOI]

Yi-Jun Chang

Jan Studený

Theor. Comput. Sci., March, 2023

Distributed derandomization revisited.

[BibT_eX]

[DOI]

CoRR, 2023

Brief Announcement: Distributed Derandomization Revisited.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Distributed Computing, 2023

Fast Dynamic Programming in Trees in the MPC Model.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Sinkless Orientation Made Simple.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

TypeRatio: comparing competing suffixes.

[BibT_eX]

[DOI]

Dataset, January, 2022

Code for the article "New methods for analysing diachronic suffix competition across registers".

[BibT_eX]

[DOI]

Dataset, January, 2022

Data for the article "New methods for analysing diachronic suffix competition across registers".

[BibT_eX]

[DOI]

Paula Rodríguez-Puente

Tanja Säily

Dataset, January, 2022

Lexical and function words or language and text type? Abbreviation consistency in an aligned corpus of Latin and Middle English plague tracts.

[BibT_eX]

[DOI]

Alpo Honkapohja

Digit. Scholarsh. Humanit., 2022

Efficient Classification of Local Problems in Regular Trees.

[BibT_eX]

[DOI]

CoRR, 2022

Brief Announcement: Temporal Locality in Online Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Efficient Classification of Locally Checkable Problems in Regular Trees.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Sparse Matrix Multiplication in the Low-Bandwidth Model.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Local Mending.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2022

Mending Partial Solutions with Few Changes.

[BibT_eX]

[DOI]

Darya Melnyk

Neven Villani

Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

2021

Lower Bounds for Maximal Matchings and Maximal Independent Sets.

[BibT_eX]

[DOI]

J. ACM, 2021

Almost global problems in the LOCAL model.

[BibT_eX]

[DOI]

Distributed Comput., 2021

Online Algorithms with Lookaround.

[BibT_eX]

[DOI]

CoRR, 2021

Sinkless orientation is hard also in the supported LOCAL model.

[BibT_eX]

[DOI]

CoRR, 2021

Locality in Online Algorithms.

[BibT_eX]

[DOI]

CoRR, 2021

Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Locally Checkable Labelings with Small Messages.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Efficient Load-Balancing through Distributed Token Dropping.

[BibT_eX]

[DOI]

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Locally Checkable Problems in Rooted Trees.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Structural Information and Communication Complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Using Round Elimination to Understand Locality.

[BibT_eX]

[DOI]

SIGACT News, 2020

Improved distributed degree splitting and edge coloring.

[BibT_eX]

[DOI]

Distributed Comput., 2020

Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens.

[BibT_eX]

[DOI]

Yi-Jun Chang

Jan Studený

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Classification of Distributed Binary Labeling Problems.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Landscape of Locality (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems.

[BibT_eX]

[DOI]

Will Rosenbaum

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

How much does randomness help with locally checkable problems?

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Brief Announcement: Classification of Distributed Binary Labeling Problems.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Can We Automate Our Own Work - or Show That It Is Hard? (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Principles of Distributed Systems, 2020

2019

Edsger W. Dijkstra Prize in Distributed Computing 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2019

Algebraic methods in the congested clique.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Locality of Not-so-Weak Coloring.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2019

Hardness of Minimal Symmetry Breaking in Distributed Computing.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

The Distributed Complexity of Locally Checkable Problems on Paths is Decidable.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2019 Edsger W. Dijkstra Prize in Distributed Computing.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

On the Power of Preprocessing in Decentralized Network Optimization.

[BibT_eX]

[DOI]

Proceedings of the 2019 IEEE Conference on Computer Communications, 2019

2018

Node labels in local decision.

[BibT_eX]

[DOI]

Pierre Fraigniaud

Theor. Comput. Sci., 2018

The Presburger Award for Young Scientists 2019 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2018

Distributed Recoloring.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

New classes of distributed time complexity.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Towards a Complexity Theory for the Congested Clique.

[BibT_eX]

[DOI]

Janne H. Korhonen

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Changing Lanes on a Highway.

[BibT_eX]

[DOI]

Thomas Petig

Elad Michael Schiller

Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, 2018

2017

Efficient Counting with Optimal Resilience.

[BibT_eX]

[DOI]

Joel Rybicki

SIAM J. Comput., 2017

Linear-in-Δ lower bounds in the LOCAL model.

[BibT_eX]

[DOI]

Distributed Comput., 2017

Distributed Colour Reduction Revisited.

[BibT_eX]

[DOI]

CoRR, 2017

Large Cuts with Local Algorithms on Triangle-Free Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2017

Brief Announcement: Towards a Complexity Theory for the Congested Clique.

[BibT_eX]

[DOI]

Janne H. Korhonen

Proceedings of the 31st International Symposium on Distributed Computing, 2017

LCL Problems on Grids.

[BibT_eX]

[DOI]

Patric R. J. Östergård

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Constant Space and Non-Constant Time in Distributed Computing.

[BibT_eX]

[DOI]

Tuomo Lempiäinen

Proceedings of the 21st International Conference on Principles of Distributed Systems, 2017

2016

Locally Checkable Proofs in Distributed Computing.

[BibT_eX]

[DOI]

Theory Comput., 2016

Deterministic local algorithms, unique identifiers, and fractional graph colouring.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Improved Approximation Algorithms for Relay Placement.

[BibT_eX]

[DOI]

Alon Efrat

Sándor P. Fekete

Joseph S. B. Mitchell

ACM Trans. Algorithms, 2016

Synchronous counting and computational algorithm design.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Non-local Probes Do Not Help with Many Graph Problems.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Randomized Algorithms for Finding a Majority Element.

[BibT_eX]

[DOI]

Pawel Gawrychowski

Przemyslaw Uznanski

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

A lower bound for the distributed Lovász local lemma.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

The minimum backlog problem.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

Theor. Comput. Sci., 2015

Weak models of distributed computing, with connections to modal logic.

[BibT_eX]

[DOI]

Distributed Comput., 2015

Non-Local Probes Do Not Help with Graph Problems.

[BibT_eX]

[DOI]

CoRR, 2015

Locally Optimal Load Balancing.

[BibT_eX]

[DOI]

Laurent Feuilloley

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Exact Bounds for Distributed Graph Colouring.

[BibT_eX]

[DOI]

Joel Rybicki

Proceedings of the Structural Information and Communication Complexity, 2015

Towards Optimal Synchronous Counting.

[BibT_eX]

[DOI]

Joel Rybicki

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

2014

No sublogarithmic-time approximation scheme for bipartite vertex cover.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Median Filtering is Equivalent to Sorting.

[BibT_eX]

[DOI]

CoRR, 2014

Linial's Lower Bound Made Easy.

[BibT_eX]

[DOI]

Juhana Laurinharju

CoRR, 2014

Local Approximability of Minimum Dominating Set on Planar Graphs.

[BibT_eX]

[DOI]

Miikka Hilke

CoRR, 2014

Brief announcement: linial's lower bound made easy.

[BibT_eX]

[DOI]

Juhana Laurinharju

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Brief announcement: local approximability of minimum dominating set on planar graphs.

[BibT_eX]

[DOI]

Miikka Hilke

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Linear-in-delta lower bounds in the LOCAL model.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013

Lower bounds for local approximation.

[BibT_eX]

[DOI]

J. ACM, 2013

Survey of local algorithms.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2013

Synchronous Counting and Computational Algorithm Design.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2013

Exploiting locality in distributed SDN control.

[BibT_eX]

[DOI]

Stefan Schmid

Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, 2013

What can be decided locally without identifiers?

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012

Distributed maximal matching: greedy is optimal.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011

Local Approximability of Max-Min and Min-Max Linear Programs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Analysing local algorithms in location-aware quasi-unit-disk graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2011

Planar Subgraphs without Low-Degree Nodes.

[BibT_eX]

[DOI]

Evangelos Kranakis

Oscar Morales-Ponce

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Locally checkable proofs.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

2010

Local algorithms in (weakly) coloured graphs

[BibT_eX]

[DOI]

CoRR, 2010

Almost Stable Matchings by Truncating the Gale-Shapley Algorithm.

[BibT_eX]

[DOI]

Algorithmica, 2010

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks.

[BibT_eX]

[DOI]

Matti Åstrand

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Distributed algorithms for edge dominating sets.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Brief announcement: distributed almost stable marriage.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

2009

Optimisation problems in wireless sensor networks: Local algorithms and local graphs.

[BibT_eX]

[DOI]

PhD thesis, 2009

A simple local 3-approximation algorithm for vertex cover.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

A Local 2-Approximation Algorithm for the Vertex Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

An optimal local approximation algorithm for max-min linear programs.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Local Algorithms: Self-Stabilization on Speed.

[BibT_eX]

[DOI]

Roger Wattenhofer

Proceedings of the Algorithmic Methods for Distributed Cooperative Systems, 06.09., 2009

2008

Almost stable matchings in constant time

[BibT_eX]

[DOI]

CoRR, 2008

Local approximation algorithms for a class of 0/1 max-min linear programs

[BibT_eX]

[DOI]

CoRR, 2008

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

[BibT_eX]

[DOI]

Petteri Kaski

Aleksi Penttinen

Poornananda R. Gaddehosur

Ad Hoc Sens. Wirel. Networks, 2008

Approximating max-min linear programs with local algorithms.

[BibT_eX]

[DOI]

Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008

Improved Approximation Algorithms for Relay Placement.

[BibT_eX]

[DOI]

Alon Efrat

Sándor P. Fekete

Joseph S. B. Mitchell

Proceedings of the Algorithms, 2008

Optimal Backlog in the Plane.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

Tight Local Approximation Results for Max-Min Linear Programs.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2008

2007

Approximability of identifying codes and locating-dominating codes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

A distributed approximation scheme for sleep sceduling in sensor networks.

[BibT_eX]

[DOI]

Patrik Floréen

Petteri Kaski

Proceedings of the Fourth Annual IEEE Communications Society Conference on Sensor, 2007

BeTelGeuse: a tool for Bluetooth data gathering.

[BibT_eX]

[DOI]

Proceedings of the 2nd International ICST Conference on Body Area Networks, 2007

Local Approximation Algorithms for Scheduling Problems in Sensor Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks, 2007

2006

Computational Complexity of Relay Placement in Sensor Networks.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

Approximating relay placement in sensor networks.

[BibT_eX]

[DOI]

Proceedings of the 3rd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, 2006

A System for Context-Dependent User Modeling.

[BibT_eX]

[DOI]

Proceedings of the On the Move to Meaningful Internet Systems 2006: OTM 2006 Workshops, 2006

2005

Lessons Learned in the Challenge: Making Predictions and Scoring Them.

[BibT_eX]

[DOI]

Jukka Kohonen