Conference Papers

•  

A. Balliu, F. Casagrande, F. d’Amore, M. Equi, B. Keller, H. Lievonen, D. Olivetti, G. Schmid, and J. Suomela (2026) - Distributed Quantum Advantage in Locally Checkable Labeling Problems, ACM-SIAM Symposium on Discrete Algorithms (SODA), 1268--1308

A. Balliu, S. Brandt, O. Gabsdil, D. Olivetti, and J. Suomela (2026) - On the Universality of Round Elimination Fixed Points, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 5066--5092

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti, and J. Saarhelo (2025) - Towards Fully Automatic Distributed Lower Bounds, 39th International Symposium on Distributed Computing (DISC), pp 13:1--13:19

A. Balliu, S. Brandt, F. Kuhn, K. Nowicki, D. Olivetti, E. Rotenberg, and J. Suomela (2025) - Distributed Computation with Local Advice, 39th International Symposium on Distributed Computing (DISC), pp 12:1--12:19

A. Balliu, C. Coupette, A. Cruciani, F. d’Amore, M. Equi, H. Lievonen, A. Modanese, D. Olivetti, and J. Suomela (2025) - New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs, 39th International Symposium on Distributed Computing (DISC), 11:1--11:22

A. Balliu, P. Fraigniaud, D. Olivetti, and M. Rabie (2025) - Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost, ACM Symposium on Principles of Distributed Computing (PODC), pp 417--427

A. Balliu, M. Ghaffari, F. Kuhn, A. Modanese, D. Olivetti, M. Rabie, J. Suomela, and J. Uitto (2025) - Shared Randomness Helps with Local Distributed Problems, 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP), pp 16:1--16:18

A. Balliu, S. Brandt, X. Coiteux-Roy, F. d’Amore, M. Equi, F. Le Gall, H. Lievonen, A. Modanese, D. Olivetti, M-O. Renou, J. Suomela, L. Tendick, I. Veeren (2025) - Distributed Quantum Advantage for Local Problems, 57th Annual ACM Symposium on Theory of Computing (STOC), pp 451--462

A. Balliu, P. Fraigniaud, P. Lambein-Monette, D. Olivetti, M. Rabie (2024) - Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs, 38th International Symposium on Distributed Computing (DISC), pp 5:1--5:20

A. Balliu, T. Boudier, S. Brandt, D. Olivetti (2024) - Tight Lower Bounds in the Supported LOCAL Model, 2024 ACM Symposium on Principles of Distributed Computing (PODC), pp 369--379

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti, G. Schmid (2024) - Completing the Node-Averaged Complexity Landscape of LCLs on Trees, 2024 ACM Symposium on Principles of Distributed Computing (PODC), pp 369--379

A. Balliu, S. Brandt, D. Olivetti, G. Schmid (2023) - On the Node-Averaged Complexity of Locally Checkable Problems on Trees, 37th International Symposium on Distributed Computing (DISC), pp 7:1--7:21

A. Balliu, R. Latypov, Y. Maus, D. Olivetti, J. Uitto (2023) - Optimal Deterministic Massively Parallel Connectivity on Forests, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 2589--2631

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti (2023) - Distributed Maximal Matching and Maximal Independent Set on Hypergraphs, ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 2632--2676

A. Balliu, J. H. Korhonen, F. Kuhn, H. Lievonen, D. Olivetti, S. Pai, A. Paz, J. Rybicki, S. Schmid, J. Studený, J. Suomela, J. Uitto (2023) - Sinkless Orientation Made Simple, SIAM Symposium on Simplicity in Algorithms (SOSA), pp 175--191

A. Balliu, S. Brandt, M. Fischer, R. Latypov, Y. Maus, D. Olivetti, J. Uitto (2022) -  Exponential Speedup Over Locality in MPC with Optimal Memory, 36th International Symposium on Distributed Computing (DISC), to appear

A. Balliu, S. Brandt, Y-J. Chang, D. Olivetti, J. Studený, J. Suomela (2022) - Efficient Classification of Locally Checkable Problems in Regular Trees, 36th International Symposium on Distributed Computing (DISC), pp 9:1--9:21

A. Balliu, M. Ghaffari, F. Kuhn, D. Olivetti (2022) - Node and Edge Averaged Complexities of Local Graph Problems, 2022 ACM Symposium on Principles of Distributed Computing (PODC), pp 4--14

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti (2022) - Distributed Edge Coloring in Time Polylogarithmic in ∆, 2022 ACM Symposium on Principles of Distributed Computing (PODC), pp 15--25

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti (2022) - Distributed ∆-Coloring Plays Hide-and-Seek, 54th Annual ACM Symposium on Theory of Computing (STOC), pp 464--477

A. Balliu, J. Hirvonen, D. Melnyk, D. Olivetti, J. Rybicki, J.Suomela (2022) - Local Mending, 29th Structural Information and Communication Complexity (SIROCCO), pp 1--20

A. Balliu, F. Kuhn, D. Olivetti (2021) - Improved Distributed Fractional Coloring Algorithms, Proceedings of the 25th International Conference on Principles of Distributed Systems (OPODIS), pp 18:1--18:23

A. Balliu, K. Censor-Hillel, Y. Maus, D. Olivetti, J. Suomela (2021) - Locally Checkable Labelings with Small Messages, Proceedings of the 35th International Symposium on Distributed Computing (DISC), pp 8:1--8:18

A. Balliu, S. Brandt, F. Kuhn, D. Olivetti (2021) - Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees, Proceedings of the 2021 Symposium on Principles of Distributed Computing (PODC), pp 283--293

A. Balliu, S. Brandt, D. Olivetti, J. Studený, J. Suomela, A. Tereshchenko (2021) - Locally Checkable Problems in Rooted Trees, Proceedings of the 2021 Symposium on Principles of Distributed Computing (PODC), pp 263--272 

A. Balliu, S. Brandt, Y. Efron, J. Hirvonen, Y. Maus, D. Olivetti, J. Suomela (2020) - Classification of distributed binary labeling problems, Proceedings of the 34th International Symposium on Distributed Computing (DISC), pp 17:1--17:17 

A. Balliu, S. Brandt, D. Olivetti (2020) - Distributed lower bounds for ruling sets, Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS), pp 365--376

A. Balliu, S. Brandt, D. Olivetti, J. Suomela (2020) - How much does randomness help with locally checkable problems?, Proceedings of the 2020 Symposium on Principles of Distributed Computing (PODC), pp 299--308

A. Balliu, F. Kuhn, D. Olivetti (2020) - Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta, Proceedings of the 2020 Symposium on Principles of Distributed Computing (PODC), pp 289--298

A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, J. Suomela (2019) - Lower Bounds for Maximal Matchings and Maximal Independent Sets, Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pp 481--497 
FOCS 2019 Best Paper Award

A. Balliu, J. Hirvonen, C. Lenzen, D. Olivetti, J. Suomela (2019) - Locality of not-so-weak coloring, Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp 37--51

A. Balliu, S. Brandt, YJ. Chang, D. Olivetti, M. Rabie, J. Suomela (2019) - The Distributed Complexity of Locally Checkable Problems on Paths is Decidable, Proceedings of the 2019 Symposium on Principles of Distributed Computing (PODC), pp 262--271

A. Balliu, J. Hirvonen, D. Olivetti, J. Suomela (2019) - Hardness of Minimal Symmetry Breaking in Distributed Computing, Proceedings of the 2019 Symposium on Principles of Distributed Computing (PODC), pp 369--378

A. Balliu, S. Brandt, D. Olivetti, J. Suomela (2018) - Almost Global Problems in the LOCAL Model, Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pp 9:1 -- 9:16

A. Balliu, J. Hirvonen, J. H. Korhonen, T. Lempiäinen, D. Olivetti, J. Suomela (2018) - New Classes of Distributed Time Complexity, Proceedings of the 50th Symposium on the Theory of Computing (STOC), pp 1307--1318

A. Balliu, P. Fraigniaud (2017) - Certification of Compact Low-Stretch Routing Schemes, Proceedings of the 31st International Symposium on Distributed Computing (DISC), pp 6:1--6:16

A. Balliu, G. D'Angelo, P. Fraigniaud, D. Olivetti (2017) - What Can Be Verified Locally?,  Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS), pp 8:1--8:13.

A. Balliu, M. Flammini, G. Melideo, D. Olivetti (2017) - Nash Stability in Social Distance Games, Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp 342--348

A. Balliu, M. Flammini, D. Olivetti (2017) - On Pareto Optimality in Social Distance Games, Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp 349--355

A. Balliu, P. Fraigniaud, Z. Lotker, D. Olivetti (2016) - Sparsifying Congested Cliques and Core-Periphery Networks,  Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp 307--322

A. Balliu, D. Olivetti, O. Babaoglu, M. Marzolla, A. Sirbu (2014) - BiDAl: Big Data Analyzer for Cluster Traces. In Proceedings of the Workshop on System Software Support for Big Data (BigSys), pp 1781--1795