Search Results

Documents authored by Modanese, Augusto

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.16
Shared Randomness Helps with Local Distributed Problems

Authors: Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
By prior work, we have many wonderful results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in o(log n) rounds, we can speed it up to O(log^* n) rounds, and if we have a randomized algorithm that solves an LCL in O(log^* n) rounds, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity Θ(log log n) and deterministic complexity Θ(log n). However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem Π such that the round complexity of Π is Ω(√n) in the usual randomized LOCAL model (with private randomness), but if the nodes have access to a source of shared randomness, then the complexity drops to O(log n). As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem Π demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem Π also gives a separation between finitely dependent distributions and non-signaling distributions.
Cite as

Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Shared Randomness Helps with Local Distributed Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.ICALP.2025.16,
  author =	{Balliu, Alkida and Ghaffari, Mohsen and Kuhn, Fabian and Modanese, Augusto and Olivetti, Dennis and Rabie, Mika\"{e}l and Suomela, Jukka and Uitto, Jara},
  title =	{{Shared Randomness Helps with Local Distributed Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.16},
  URN =		{urn:nbn:de:0030-drops-233931},
  doi =		{10.4230/LIPIcs.ICALP.2025.16},
  annote =	{Keywords: Distributed computing, locally checkable labelings, shared randomness}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.27
Local Problems in Trees Across a Wide Range of Distributed Models

Authors: Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Muftuoglu, Jan Studený, and Jukka Suomela

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
The randomized online-LOCAL model captures a number of models of computing; it is at least as strong as all of these models: - the classical LOCAL model of distributed graph algorithms, - the quantum version of the LOCAL model, - finitely dependent distributions [e.g. Holroyd 2016], - any model that does not violate physical causality [Gavoille, Kosowski, Markiewicz, DISC 2009], - the SLOCAL model [Ghaffari, Kuhn, Maus, STOC 2017], and - the dynamic-LOCAL and online-LOCAL models [Akbari et al., ICALP 2023]. In general, the online-LOCAL model can be much stronger than the LOCAL model. For example, there are locally checkable labeling problems (LCLs) that can be solved with logarithmic locality in the online-LOCAL model but that require polynomial locality in the LOCAL model. However, in this work we show that in trees, many classes of LCL problems have the same locality in deterministic LOCAL and randomized online-LOCAL (and as a corollary across all the above-mentioned models). In particular, these classes of problems do not admit any distributed quantum advantage. We present a near-complete classification for the case of rooted regular trees. We also fully classify the super-logarithmic region in unrooted regular trees. Finally, we show that in general trees (rooted or unrooted, possibly irregular, possibly with input labels) problems that are global in deterministic LOCAL remain global also in the randomized online-LOCAL model.
Cite as

Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Muftuoglu, Jan Studený, and Jukka Suomela. Local Problems in Trees Across a Wide Range of Distributed Models. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dhar_et_al:LIPIcs.OPODIS.2024.27,
  author =	{Dhar, Anubhav and Kujawa, Eli and Lievonen, Henrik and Modanese, Augusto and Muftuoglu, Mikail and Studen\'{y}, Jan and Suomela, Jukka},
  title =	{{Local Problems in Trees Across a Wide Range of Distributed Models}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.27},
  URN =		{urn:nbn:de:0030-drops-225633},
  doi =		{10.4230/LIPIcs.OPODIS.2024.27},
  annote =	{Keywords: Distributed algorithms, quantum-LOCAL model, randomized online-LOCAL model, locally checkable labeling problems, trees}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.112
Testing Spreading Behavior in Networks with Arbitrary Topologies

Authors: Augusto Modanese and Yuichi Yoshida

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Given the full topology of a network, how hard is it to test if it is evolving according to a local rule or is far from doing so? Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every "infected" node stays infected forever, and each "healthy" node becomes infected if and only if it has at least one infected neighbor. Our results are subdivided into two main groups: - If we are testing a single time step of evolution, then the query complexity is O(Δ/ε) or Õ(√n/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and the number of vertices in the underlying graph, respectively. We also give lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ = o(√n) and Δ = O(n^{1/3}), respectively. If ε is constant, then the first of these also holds against adaptive testers. - When testing the environment over T time steps, we have two algorithms that need O(Δ^{T-1}/εT) and Õ(|E|/εT) queries, respectively, where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T = 2.
Cite as

Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 112:1-112:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{modanese_et_al:LIPIcs.ICALP.2024.112,
  author =	{Modanese, Augusto and Yoshida, Yuichi},
  title =	{{Testing Spreading Behavior in Networks with Arbitrary Topologies}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{112:1--112:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.112},
  URN =		{urn:nbn:de:0030-drops-202554},
  doi =		{10.4230/LIPIcs.ICALP.2024.112},
  annote =	{Keywords: Property testing, bootstrap percolation, local phenomena, expander graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.47
Sublinear-Time Probabilistic Cellular Automata

Authors: Augusto Modanese

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes RP and BPP) and establish a separation between the classes of languages they can recognize all the way up to o(√n) time. As a consequence, we have a Ω(√n) lower bound for derandomizing constant-time one-sided error PACAs (using deterministic ACAs). We also prove that derandomization of T(n)-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of T(n) = ω(log n) implies non-trivial derandomization results for the class RP (e.g., P = RP). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages (LLT) and prove that the languages decidable by constant-time two-sided error PACAs are "sandwiched" in-between the closure of LLT under union and intersection and the class of locally threshold testable languages (LTT).
Cite as

Augusto Modanese. Sublinear-Time Probabilistic Cellular Automata. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{modanese:LIPIcs.STACS.2023.47,
  author =	{Modanese, Augusto},
  title =	{{Sublinear-Time Probabilistic Cellular Automata}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.47},
  URN =		{urn:nbn:de:0030-drops-176998},
  doi =		{10.4230/LIPIcs.STACS.2023.47},
  annote =	{Keywords: Cellular automata, local computation, probabilistic models, subregular language classes}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact