default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAlkida Balliu
Person information
- affiliation: Gran Sasso Science Institute, L'Aquila, Italy
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2023
[j12]Alkida Balliu
, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko:
Locally checkable problems in rooted trees. Distributed Comput. 36(3): 277-311 (2023)- [j11]Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti:
Node and edge averaged complexities of local graph problems. Distributed Comput. 36(4): 451-473 (2023) - [j10]Dan Alistarh, Alkida Balliu, Dimitrios Los, Sean Ovens:
A Brief Summary of PODC 2022. SIGACT News 54(1): 106-112 (2023) - 2022
- [j9]Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti:
On Pareto optimality in social distance games. Artif. Intell. 312: 103768 (2022) - [j8]Alkida Balliu, Sebastian Brandt, Dennis Olivetti:
Distributed Lower Bounds for Ruling Sets. SIAM J. Comput. 51(1): 70-115 (2022) - 2021
- [j7]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela:
Almost global problems in the LOCAL model. Distributed Comput. 34(4): 259-281 (2021) - [j6]Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
Lower Bounds for Maximal Matchings and Maximal Independent Sets. J. ACM 68(5): 39:1-39:30 (2021) - 2020
- [j5]Mirza Ahad Baig, Alkida Balliu, Peter Davies, Michal Dory:
PODC 2020 Review. SIGACT News 51(4): 75-81 (2020) - 2019
- [j4]Alkida Balliu, Pierre Fraigniaud:
Certification of Compact Low-Stretch Routing Schemes. Comput. J. 62(5): 730-746 (2019) - [j3]Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti:
On Non-Cooperativeness in Social Distance Games. J. Artif. Intell. Res. 66: 625-653 (2019) - 2018
- [j2]Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti:
What can be verified locally? J. Comput. Syst. Sci. 97: 106-120 (2018) - 2016
- [j1]Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu:
A Big Data analyzer for large trace logs. Computing 98(12): 1225-1249 (2016)
Conference and Workshop Papers
- 2024
- [c35]Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti:
Tight Lower Bounds in the Supported LOCAL Model. PODC 2024: 95-105 - [c34]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela:
Brief Announcement: Local Advice and Local Decompression. PODC 2024: 117-120 - [c33]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid:
Completing the Node-Averaged Complexity Landscape of LCLs on Trees. PODC 2024: 369-379 - [c32]Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, Mikaël Rabie:
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs. DISC 2024: 5:1-5:20 - 2023
- [c31]Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto:
Optimal Deterministic Massively Parallel Connectivity on Forests. SODA 2023: 2589-2631 - [c30]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. SODA 2023: 2632-2676 - [c29]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:
Sinkless Orientation Made Simple. SOSA 2023: 175-191 - [c28]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid:
On the Node-Averaged Complexity of Locally Checkable Problems on Trees. DISC 2023: 7:1-7:21 - 2022
- [c27]Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti:
Node and Edge Averaged Complexities of Local Graph Problems. PODC 2022: 4-14 - [c26]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed Edge Coloring in Time Polylogarithmic in Δ. PODC 2022: 15-25 - [c25]Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, Jukka Suomela:
Local Mending. SIROCCO 2022: 1-20 - [c24]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed ∆-coloring plays hide-and-seek. STOC 2022: 464-477 - [c23]Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela:
Efficient Classification of Locally Checkable Problems in Regular Trees. DISC 2022: 8:1-8:19 - [c22]Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto:
Exponential Speedup over Locality in MPC with Optimal Memory. DISC 2022: 9:1-9:21 - 2021
- [c21]Alkida Balliu, Fabian Kuhn, Dennis Olivetti:
Improved Distributed Fractional Coloring Algorithms. OPODIS 2021: 18:1-18:23 - [c20]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko:
Locally Checkable Problems in Rooted Trees. PODC 2021: 263-272 - [c19]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. PODC 2021: 283-293 - [c18]Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, Jukka Suomela:
Locally Checkable Labelings with Small Messages. DISC 2021: 8:1-8:18 - 2020
- [c17]Alkida Balliu, Sebastian Brandt, Dennis Olivetti:
Distributed Lower Bounds for Ruling Sets. FOCS 2020: 365-376 - [c16]Alkida Balliu, Fabian Kuhn, Dennis Olivetti:
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta. PODC 2020: 289-298 - [c15]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela:
How much does randomness help with locally checkable problems? PODC 2020: 299-308 - [c14]Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela:
Brief Announcement: Classification of Distributed Binary Labeling Problems. PODC 2020: 349-351 - [c13]Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela:
Classification of Distributed Binary Labeling Problems. DISC 2020: 17:1-17:17 - 2019
- [c12]Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
Lower Bounds for Maximal Matchings and Maximal Independent Sets. FOCS 2019: 481-497 - [c11]Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
The Distributed Complexity of Locally Checkable Problems on Paths is Decidable. PODC 2019: 262-271 - [c10]Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela:
Hardness of Minimal Symmetry Breaking in Distributed Computing. PODC 2019: 369-378 - [c9]Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela:
Locality of Not-so-Weak Coloring. SIROCCO 2019: 37-51 - 2018
- [c8]Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela:
New classes of distributed time complexity. STOC 2018: 1307-1318 - [c7]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela:
Almost Global Problems in the LOCAL Model. DISC 2018: 9:1-9:16 - 2017
- [c6]Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti:
Nash Stability in Social Distance Games. AAAI 2017: 342-348 - [c5]Alkida Balliu, Michele Flammini, Dennis Olivetti:
On Pareto Optimality in Social Distance Games. AAAI 2017: 349-355 - [c4]Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti:
What Can Be Verified Locally?. STACS 2017: 8:1-8:13 - [c3]Alkida Balliu, Pierre Fraigniaud:
Certification of Compact Low-Stretch Routing Schemes. DISC 2017: 6:1-6:16 - 2016
- [c2]Alkida Balliu, Pierre Fraigniaud, Zvi Lotker, Dennis Olivetti:
Sparsifying Congested Cliques and Core-Periphery Networks. SIROCCO 2016: 307-322 - 2014
- [c1]Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu:
BiDAl: Big Data Analyzer for Cluster Traces. GI-Jahrestagung 2014: 1781-1795
Editorship
- 2023
- [e2]Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, Alkida Balliu:
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023. ACM 2023 [contents] - [e1]Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, Dennis Olivetti:
Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings. Lecture Notes in Computer Science 13892, Springer 2023, ISBN 978-3-031-32732-2 [contents]
Informal and Other Publications
- 2025
- [i37]Alkida Balliu, Filippo Casagrande, Francesco D'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela:
Distributed Quantum Advantage in Locally Checkable Labeling Problems. CoRR abs/2504.05191 (2025) - 2024
- [i36]Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti:
Tight Lower Bounds in the Supported LOCAL Model. CoRR abs/2405.00825 (2024) - [i35]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid:
Completing the Node-Averaged Complexity Landscape of LCLs on Trees. CoRR abs/2405.01366 (2024) - [i34]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela:
Local Advice and Local Decompression. CoRR abs/2405.04519 (2024) - [i33]Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Jara Uitto:
Shared Randomness Helps with Local Distributed Problems. CoRR abs/2407.05445 (2024) - [i32]Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, Mikaël Rabie:
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs. CoRR abs/2408.10971 (2024) - [i31]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Joonatan Saarhelo:
Towards Fully Automatic Distributed Lower Bounds. CoRR abs/2410.20224 (2024) - [i30]Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, Mikaël Rabie:
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost. CoRR abs/2410.20499 (2024) - [i29]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:
Distributed Quantum Advantage for Local Problems. CoRR abs/2411.03240 (2024) - 2023
- [i28]Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, Laurent Viennot:
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs. CoRR abs/2304.00817 (2023) - [i27]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Gustav Schmid:
On the Node-Averaged Complexity of Locally Checkable Problems on Trees. CoRR abs/2308.04251 (2023) - 2022
- [i26]Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela:
Efficient Classification of Local Problems in Regular Trees. CoRR abs/2202.08544 (2022) - [i25]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed Edge Coloring in Time Polylogarithmic in Δ. CoRR abs/2206.00976 (2022) - [i24]Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti:
Node and Edge Averaged Complexities of Local Graph Problems. CoRR abs/2208.08213 (2022) - [i23]Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto:
Exponential Speedup Over Locality in MPC with Optimal Memory. CoRR abs/2208.09453 (2022) - [i22]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs. CoRR abs/2211.01945 (2022) - [i21]Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, Jara Uitto:
Optimal Deterministic Massively Parallel Connectivity on Forests. CoRR abs/2211.03530 (2022) - 2021
- [i20]Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, Jukka Suomela:
Local Mending. CoRR abs/2102.08703 (2021) - [i19]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko:
Locally Checkable Problems in Rooted Trees. CoRR abs/2102.09277 (2021) - [i18]Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, Jukka Suomela:
Locally Checkable Labelings with Small Messages. CoRR abs/2105.05574 (2021) - [i17]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. CoRR abs/2106.02440 (2021) - [i16]Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti:
Distributed Δ-Coloring Plays Hide-and-Seek. CoRR abs/2110.00643 (2021) - [i15]Alkida Balliu, Fabian Kuhn, Dennis Olivetti:
Improved Distributed Fractional Coloring Algorithms. CoRR abs/2112.04405 (2021) - 2020
- [i14]Alkida Balliu, Fabian Kuhn, Dennis Olivetti:
Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta. CoRR abs/2002.10780 (2020) - [i13]Alkida Balliu, Sebastian Brandt, Dennis Olivetti:
Distributed Lower Bounds for Ruling Sets. CoRR abs/2004.08282 (2020) - 2019
- [i12]Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
Lower bounds for maximal matchings and maximal independent sets. CoRR abs/1901.02441 (2019) - [i11]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela:
How much does randomness help with locally checkable problems? CoRR abs/1902.06803 (2019) - [i10]Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela:
Locality of not-so-weak coloring. CoRR abs/1904.05627 (2019) - [i9]Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela:
Classification of distributed binary labeling problems. CoRR abs/1911.13294 (2019) - 2018
- [i8]Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela:
Almost Global Problems in the LOCAL Model. CoRR abs/1805.04776 (2018) - [i7]Alkida Balliu, Juho Hirvonen, Dennis Olivetti, Jukka Suomela:
Hardness of minimal symmetry breaking in distributed computing. CoRR abs/1811.01643 (2018) - [i6]Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela:
The distributed complexity of locally checkable problems on paths is decidable. CoRR abs/1811.01672 (2018) - 2017
- [i5]Alkida Balliu, Pierre Fraigniaud:
Certification of Compact Low-Stretch Routing Schemes. CoRR abs/1704.06070 (2017) - [i4]Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela:
New Classes of Distributed Time Complexity. CoRR abs/1711.01871 (2017) - 2016
- [i3]Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti:
Local Distributed Verification. CoRR abs/1605.03892 (2016) - 2015
- [i2]Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu:
A Big Data Analyzer for Large Trace Logs. CoRR abs/1509.00773 (2015) - 2014
- [i1]Alkida Balliu, Dennis Olivetti, Özalp Babaoglu, Moreno Marzolla, Alina Sîrbu:
BiDAl: Big Data Analyzer for Cluster Traces. CoRR abs/1410.1309 (2014)
Coauthor Index
[j12] [j11] [j9] [j8] [j7] [j6] [j3] [j2] [j1] [c35] [c34] [c33] [c32] [c31] [c30] [c29] [c28] [c27] [c26] [c25] [c24] [c23] [c22] [c21] [c20] [c19] [c18] [c17] [c16] [c15] [c14] [c13] [c12] [c11] [c10] [c9] [c8] [c7] [c6] [c5] [c4] [c2] [c1] [e1] [i37] [i36] [i35] [i34] [i33] [i32] [i31] [i30] [i29] [i28] [i27] [i26] [i25] [i24] [i23] [i22] [i21] [i20] [i19] [i18] [i17] [i16] [i15] [i14] [i13] [i12] [i11] [i10] [i9] [i8] [i7] [i6] [i4] [i3] [i2] [i1]
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-05-22 00:45 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
