Alkida Balliu

100 papers A* 27A 12B 5Journal 54Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A* conf
Distributed Quantum Advantage in Locally Checkable Labeling Problems.
SODA
Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela
2026 A* conf
On the Universality of Round Elimination Fixed Points.
SODA
Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
2025 J jnl
Distributed Algorithms for Potential Problems.
CoRR
Alkida Balliu, Thomas Boudier, Francesco d'Amore, Dennis Olivetti, Gustav Schmid, Jukka Suomela
2025 A conf
Distributed Computation with Local Advice.
DISC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2025 A* conf
Distributed Quantum Advantage for Local Problems.
STOC
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
2025 J jnl
Distributed Quantum Advantage in Locally Checkable Labeling Problems.
CoRR
Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela
2025 J jnl
Exponential speedup over locality in MPC with optimal memory.
Distributed Comput.
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2025 J jnl
New Hardness Results for the LOCAL Model via a Simple Self-Reduction.
CoRR
Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Dennis Olivetti
2025 A conf
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs.
DISC
Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Jukka Suomela
2025 J jnl
New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs.
CoRR
Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d'Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Jukka Suomela
2025 J jnl
On the Universality of Round Elimination Fixed Points.
CoRR
Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
2025 A* ed.
Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, Hotel Las Brisas Huatulco, Huatulco, Mexico, June 16-20, 2025
PODC
Alkida Balliu, Fabian Kuhn
2025 A* conf
Shared Randomness Helps with Local Distributed Problems.
ICALP
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Jara Uitto
2025 A* conf
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost.
PODC
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, Mikaël Rabie
2025 A conf
Towards Fully Automatic Distributed Lower Bounds.
DISC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Joonatan Saarhelo
2024 A conf
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs.
DISC
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, Mikaël Rabie
2024 J jnl
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs.
CoRR
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, Mikaël Rabie
2024 A* conf
Brief Announcement: Local Advice and Local Decompression.
PODC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2024 A* conf
Completing the Node-Averaged Complexity Landscape of LCLs on Trees.
PODC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2024 J jnl
Completing the Node-Averaged Complexity Landscape of LCLs on Trees.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2024 J jnl
Distributed Quantum Advantage for Local Problems.
CoRR
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
2024 J jnl
Local Advice and Local Decompression.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
2024 J jnl
Shared Randomness Helps with Local Distributed Problems.
CoRR
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Jara Uitto
2024 J jnl
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost.
CoRR
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, Mikaël Rabie
2024 A* conf
Tight Lower Bounds in the Supported LOCAL Model.
PODC
Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
2024 J jnl
Tight Lower Bounds in the Supported LOCAL Model.
CoRR
Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti
2024 J jnl
Towards Fully Automatic Distributed Lower Bounds.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Joonatan Saarhelo
2023 J jnl
A Brief Summary of PODC 2022.
SIGACT News
Dan Alistarh, Alkida Balliu, Dimitrios Los, Sean Ovens
2023 J jnl
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs.
CoRR
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, Laurent Viennot
2023 A* conf
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs.
SODA
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2023 J jnl
Locally checkable problems in rooted trees.
Distributed Comput.
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2023 J jnl
Node and edge averaged complexities of local graph problems.
Distributed Comput.
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti
2023 A conf
On the Node-Averaged Complexity of Locally Checkable Problems on Trees.
DISC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2023 J jnl
On the Node-Averaged Complexity of Locally Checkable Problems on Trees.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid
2023 A* conf
Optimal Deterministic Massively Parallel Connectivity on Forests.
SODA
Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2023 A* ed.
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023
PODC
Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, Alkida Balliu
2023 — conf
Sinkless Orientation Made Simple.
SOSA
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto
2023 B ed.
Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings
SIROCCO
Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, Dennis Olivetti
2022 A* conf
Distributed Edge Coloring in Time Polylogarithmic in Δ.
PODC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022 J jnl
Distributed Edge Coloring in Time Polylogarithmic in Δ.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022 J jnl
Distributed Lower Bounds for Ruling Sets.
SIAM J. Comput.
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2022 J jnl
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022 A* conf
Distributed ∆-coloring plays hide-and-seek.
STOC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2022 J jnl
Efficient Classification of Local Problems in Regular Trees.
CoRR
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
2022 A conf
Efficient Classification of Locally Checkable Problems in Regular Trees.
DISC
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela
2022 J jnl
Exponential Speedup Over Locality in MPC with Optimal Memory.
CoRR
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2022 A conf
Exponential Speedup over Locality in MPC with Optimal Memory.
DISC
Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2022 B conf
Local Mending.
SIROCCO
Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, Jukka Suomela
2022 A* conf
Node and Edge Averaged Complexities of Local Graph Problems.
PODC
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti
2022 J jnl
Node and Edge Averaged Complexities of Local Graph Problems.
CoRR
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti
2022 J jnl
On Pareto optimality in social distance games.
Artif. Intell.
Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti
2022 J jnl
Optimal Deterministic Massively Parallel Connectivity on Forests.
CoRR
Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto
2021 J jnl
Almost global problems in the LOCAL model.
Distributed Comput.
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2021 J jnl
Distributed Δ-Coloring Plays Hide-and-Seek.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021 B conf
Improved Distributed Fractional Coloring Algorithms.
OPODIS
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
2021 J jnl
Improved Distributed Fractional Coloring Algorithms.
CoRR
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
2021 A* conf
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees.
PODC
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021 J jnl
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees.
CoRR
Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti
2021 J jnl
Local Mending.
CoRR
Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, Jukka Suomela
2021 A conf
Locally Checkable Labelings with Small Messages.
DISC
Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, Jukka Suomela
2021 J jnl
Locally Checkable Labelings with Small Messages.
CoRR
Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, Jukka Suomela
2021 A* conf
Locally Checkable Problems in Rooted Trees.
PODC
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2021 J jnl
Locally Checkable Problems in Rooted Trees.
CoRR
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko
2021 J jnl
Lower Bounds for Maximal Matchings and Maximal Independent Sets.
J. ACM
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2020 A* conf
Brief Announcement: Classification of Distributed Binary Labeling Problems.
PODC
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2020 A conf
Classification of Distributed Binary Labeling Problems.
DISC
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2020 A* conf
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta.
PODC
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
2020 J jnl
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta.
CoRR
Alkida Balliu, Fabian Kuhn, Dennis Olivetti
2020 A* conf
Distributed Lower Bounds for Ruling Sets.
FOCS
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2020 J jnl
Distributed Lower Bounds for Ruling Sets.
CoRR
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
2020 A* conf
How much does randomness help with locally checkable problems?
PODC
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2020 J jnl
PODC 2020 Review.
SIGACT News
Mirza Ahad Baig, Alkida Balliu, Peter Davies, Michal Dory
2019 J jnl
Certification of Compact Low-Stretch Routing Schemes.
Comput. J.
Alkida Balliu, Pierre Fraigniaud
2019 J jnl
Classification of distributed binary labeling problems.
CoRR
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela
2019 A* conf
Hardness of Minimal Symmetry Breaking in Distributed Computing.
PODC
Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela
2019 J jnl
How much does randomness help with locally checkable problems?
CoRR
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2019 B conf
Locality of Not-so-Weak Coloring.
SIROCCO
Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela
2019 J jnl
Locality of not-so-weak coloring.
CoRR
Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela
2019 A* conf
Lower Bounds for Maximal Matchings and Maximal Independent Sets.
FOCS
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2019 J jnl
Lower bounds for maximal matchings and maximal independent sets.
CoRR
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2019 J jnl
On Non-Cooperativeness in Social Distance Games.
J. Artif. Intell. Res.
Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti
2019 A* conf
The Distributed Complexity of Locally Checkable Problems on Paths is Decidable.
PODC
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2018 A conf
Almost Global Problems in the LOCAL Model.
DISC
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2018 J jnl
Almost Global Problems in the LOCAL Model.
CoRR
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela
2018 J jnl
Hardness of minimal symmetry breaking in distributed computing.
CoRR
Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela
2018 A* conf
New classes of distributed time complexity.
STOC
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela
2018 J jnl
The distributed complexity of locally checkable problems on paths is decidable.
CoRR
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela
2018 J jnl
What can be verified locally?
J. Comput. Syst. Sci.
Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti
2017 A conf
Certification of Compact Low-Stretch Routing Schemes.
DISC
Alkida Balliu, Pierre Fraigniaud
2017 J jnl
Certification of Compact Low-Stretch Routing Schemes.
CoRR
Alkida Balliu, Pierre Fraigniaud
2017 A* conf
Nash Stability in Social Distance Games.
AAAI
Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti
2017 J jnl
New Classes of Distributed Time Complexity.
CoRR
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela
2017 A* conf
On Pareto Optimality in Social Distance Games.
AAAI
Alkida Balliu, Michele Flammini, Dennis Olivetti
2017 A conf
What Can Be Verified Locally?.
STACS
Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti
2016 J jnl
A Big Data analyzer for large trace logs.
Computing
Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu
2016 J jnl
Local Distributed Verification.
CoRR
Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti
2016 B conf
Sparsifying Congested Cliques and Core-Periphery Networks.
SIROCCO
Alkida Balliu, Pierre Fraigniaud, Zvi Lotker, Dennis Olivetti
2015 J jnl
A Big Data Analyzer for Large Trace Logs.
CoRR
Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu
2014 — conf
BiDAl: Big Data Analyzer for Cluster Traces.
GI-Jahrestagung
Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu
2014 J jnl
BiDAl: Big Data Analyzer for Cluster Traces.
CoRR
Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu