Jukka Suomela

Theor. Comput. Sci., January, 2024

Online Locality Meets Distributed Quantum Computing.

[BibT_eX]

[DOI]

CoRR, 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 Binary Labeling Problems in High-Degree Graphs.

[BibT_eX]

[DOI]

Henrik Lievonen

Timothé Picavet

CoRR, 2023

No distributed quantum advantage for approximate graph coloring.

[BibT_eX]

[DOI]

CoRR, 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

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