*Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany*, volume 261 of *LIPIcs*, pages 10:1–10:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ICALP.2023.10.

[3] Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? *SIGACT News*, 45(3):82–104, 2014. doi:10.1145/2670418.2670440.

[4] Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018*, pages 1307–1318. ACM, 2018. doi:10.1145/3188745.3188860.

[5] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In Peter Robinson and Faith Ellen, editors, *Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019*, pages 262–271. ACM, 2019. doi:10.1145/3293611.3331606.

[6] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In Yuval Emek and Christian Cachin, editors, *PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020*, pages 299–308. ACM, 2020. doi:10.1145/3382734.3405715.

[7] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. *Journal of the ACM*, 68(5):39:1–39:30, 2021. doi:10.1145/3461458.

[8] Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. *Distributed Computing*, 34(4):259–281, 2021. doi:10.1007/S00446-020-00375-2.

[9] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela. Efficient classification of locally checkable problems in regular trees. In Christian Scheideler, editor, *36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA*, volume 246 of *LIPIcs*, pages 8:1–8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.DISC.2022.8.

[10] Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela. Local mending. In Merav Parter, editor, *Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27-29, 2022, Proceedings*, volume 13298 of *Lecture Notes in Computer Science*, pages 1–20. Springer, 2022. doi:10.1007/978-3-031-09993-9_1.

[11] Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. *Distributed Computing*, 36(3):277–311, 2023. doi:10.1007/S00446-022-00435-9.

[12] Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, and Jara Uitto. Sinkless orientation made simple. In Telikepalli Kavitha and Kurt Mehlhorn, editors, *2023 Symposium*
on Simplicity in Algorithms, SOSA 2023, Florence, Italy, January 23-25, 2023, pages 175-191.
SIAM, 2023. doi:10.1137/1.9781611977585.CH17.

[13] 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, 2024. URL https://arxiv.org/abs/2407.05445.

[14] Salman Beigi and Marc-Olivier Renou. Covariance decomposition as a universal limit on correlations in networks. *IEEE Transactions on Information Theory*, 68(1):384-394, 2021.

[15] Max Born. Quantenmechanik der Stoßvorgänge. *Zeitschrift für Physik*, 38(11-12):803-827, 1926.
doi:10.1007/bf01397184.

[16] Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In Daniel Wichs and Yishay Mansour, editors, *Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016*, pages 479-488. ACM, 2016. doi:10.1145/2897518.2897570.

[17] Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznanski. LCL problems on grids. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, *Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017*, pages 101-110. ACM, 2017. doi:10.1145/3087801.3087833.

[18] Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum distributed algorithms for detection of cliques. In Mark Braverman, editor, *13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA*, volume 215 of *LIPIcs*, pages 35:1-35:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ITCS.2022.35.

[19] Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. *SIAM Journal on Computing*, 48(1):33-69, 2019. doi:10.1137/17M1157957.

[20] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Irit Dinur, editor, *IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA*, pages 615-624. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.72.

[21] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. *SIAM Journal on Computing*, 48(1):122-143, 2019. doi:10.1137/17M1117537.

[22] Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, Mingyang Yang, and Yu-Cheng Yeh. A tight lower bound for 3-coloring grids in the online-LOCAL model. CoRR, abs/2312.01384, 2023. doi:10.48550/ARXIV.2312.01384.

[23] Yi-Jun Chang, Jan Studený, and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. *Theoretical Computer Science*, 951:113710, 2023. doi:10.1016/J.TCS.2023.113710.
[24] Giulio Chiribella and Robert W. Spekkens, editors. *Quantum Theory: Informational Foundations and Foils*. Springer Netherlands, 2016. doi:10.1007/978-94-017-7303-4.

[25] Xavier Coiteux-Roy, Elie Wolfe, and Marc-Olivier Renou. Any physical theory of nature must be boundlessly multipartite nonlocal. *Physical Review A*, 104(5):052207, 2021.

[26] Xavier Coiteux-Roy, Elie Wolfe, and Marc-Olivier Renou. No Bipartite-Nonlocal Causal Theory Can Explain Nature's Correlations. *Physical Review Letters*, 127(20):200401, 2021. doi:10.1103/physrevlett.127.200401.

[27] Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. In *Proc. 56th Annual ACM Symposium on Theory of Computing (STOC 2024)*. ACM Press, 2024.

[28] Xavier Coiteux-Roy, Owidiusz Makuta, Fionnuala Curran, Remigiusz Augusiak, and Marc-Olivier Renou. The genuinely multipartite nonlocality of graph states is model-dependent, 2024. In preparation.

[29] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. *Information and Control*, 70(1):32–53, 1986. doi:10.1016/S0019-9958(86)80023-7.

[30] Sameep Dahal, Francesco D'Amore, Henrik Lievonen, Timothé Picavet, and Jukka Suomela. Brief announcement: Distributed derandomization revisited. In Rotem Oshman, editor, *37th International Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L'Aquila, Italy*, volume 281 of *LIPIcs*, pages 40:1–40:5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.DISC.2023.40.

[31] Giacomo Mauro D'Ariano, Giulio Chiribella, and Paolo Perinotti. *Quantum Theory from First Principles: An Informational Approach*. Cambridge University Press, 2016. doi:10.1017/9781107338340.

[32] 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 *Proc. 28th International Conference on Principles of Distributed Systems (OPODIS 2024)*, Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2024.

[33] Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Magnús M. Halldórsson and Shlomi Dolev, editors, *ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014*, pages 166–175. ACM, 2014. doi:10.1145/2611462.2611488.

[34] Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy. In Andréa W. Richa, editor, *31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria*, volume 91 of *LIPIcs*, pages 18:1–18:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPICS.DISC.2017.18.

[35] Pierre Fraigniaud, Maël Luce, Frédéric Magniez, and Ioan Todinca. Even-cycle detection in the randomized and quantum CONGEST model. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, *Proceedings of the 43rd ACM Symposium on Principles of Distributed Theory*
*Computing*, PODC 2024, Nantes, France, June 17-21, 2024, pages 209-219. ACM, 2024.
doi:10.1145/3662158.3662767.

[36] Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In Idit Keidar, editor, *Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings*, volume 5805 of *Lecture Notes in Computer Science*, pages 243-257. Springer, 2009. doi:10.1007/978-3-642-04355-0_26.

[37] Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Philip N. Klein, editor, *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19*, pages 2505-2523. SIAM, 2017. doi:10.1137/1.9781611974782.166.

[38] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017*, pages 784-797. ACM, 2017. doi:10.1145/3055399.3055471.

[39] Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Mikkel Thorup, editor, *59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018*, pages 662-673. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00069.

[40] Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. *Distributed Computing*, 33(3-4):293-310, 2020. doi:10.1007/S00446-018-00346-8.

[41] Nicolas Gisin, Jean-Daniel Bancal, Yu Cai, Patrick Remy, Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Sandu Popescu, and Nicolas Brunner. Constraints on nonlocality in networks from no-signaling and independence. *Nature Communications*, 11(1):2378, 2020. doi:10.1038/s41467-020-16137-4.

[42] Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel symmetry-breaking in sparse graphs. *SIAM Journal on Discrete Mathematics*, 1(4):434-446, 1988. doi:10.1137/0401044.

[43] Atsuya Hasegawa, Srijita Kundu, and Harumichi Nishimura. On the power of quantum distributed proofs. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, *Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024*, pages 220-230. ACM, 2024. doi:10.1145/3662158.3662788.

[44] Alexander E. Holroyd. Symmetrization for finitely dependent colouring. *Electronic Communications in Probability*, 29, 2024. doi:10.1214/24-ecp600.

[45] Alexander E. Holroyd and Thomas M. Liggett. Finitely Dependent Coloring. *Forum of Mathematics, Pi*, 4:e9, 2016. doi:10.1017/fmp.2016.7.

[46] Alexander E. Holroyd, Oded Schramm, and David B. Wilson. Finitary coloring. *The Annals of Probability*, 45(5):2867-2898, 2017. doi:10.1214/16-aop1127.

[47] Alexander E. Holroyd, Tom Hutchcroft, and Avi Levy. Finitely dependent cycle coloring. *Electronic Communications in Probability*, 23, 2018. doi:10.1214/18-ecp118.
[48] Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the CONGEST-CLIQUE model. In Peter Robinson and Faith Ellen, editors, *Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019*, pages 84–93. ACM, 2019. doi:10.1145/3293611.3331628.

[49] Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In Christophe Paul and Markus Bläser, editors, *37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France*, volume 154 of LIPIcs, pages 23:1–23:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.STACS.2020.23.

[50] Amos Korman, Jean-Sébastien Sereni, and Laurent Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. *Distributed Computing*, 26 (5-6):289–308, 2013. doi:10.1007/S00446-012-0174-8.

[51] François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In *Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing*, pages 337–346. ACM, 2018. doi:10.1145/3212734.3212744.

[52] François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In Rolf Niedermeier and Christophe Paul, editors, *36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany*, volume 126 of LIPIcs, pages 49:1–49:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.STACS.2019.49.

[53] Nathan Linial. Distributive graph algorithms-global solutions from local data. In *28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987*, pages 331–335. IEEE Computer Society, 1987. doi:10.1109/SFCS.1987.20.

[54] Nathan Linial. Locality in distributed graph algorithms. *SIAM Journal on Computing*, 21(1): 193–201, 1992. doi:10.1137/0221015.

[55] Frédéric Magniez and Ashwin Nayak. Quantum distributed complexity of set disjointness on a line. *ACM Transactions on Computation Theory*, 14(1):5:1–5:22, 2022. doi:10.1145/3512751.

[56] Yannic Maus and Tigran Tonoyan. Linial for lists. *Distributed Computing*, 35(6):533–546, 2022. doi:10.1007/S00446-022-00424-Y.

[57] Moni Naor and Larry J. Stockmeyer. What can be computed locally? *SIAM Journal on Computing*, 24(6):1259–1277, 1995. doi:10.1137/S0097539793254571.

[58] Michael A. Nielsen and Isaac L. Chuang. *Quantum Computation and Quantum Information: 10th Anniversary Edition*. Cambridge University Press, 2012. doi:10.1017/cbo9780511976667.

[59] Dennis Olivetti. Round eliminator: a tool for automatic speedup simulation, 2019. URL https://github.com/olidennis/round-eliminator.

[60] Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. *Distributed Computing*, 14(2):97–100, 2001. doi:10.1007/PL00008932.

[61] David Peleg. *Distributed Computing: A Locality-Sensitive Approach*. Society for Industrial and Applied Mathematics, 2000. doi:10.1137/1.9780898719772.
[62] Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020*, pages 350-363. ACM, 2020. doi:10.1145/3357713.3384298.

[63] Yinon Spinka. Finitely dependent processes are finitary. *The Annals of Probability*, 48(4): 2088-2117, 2020. doi:10.1214/19-aop1417.

[64] Jukka Suomela. Landscape of locality (invited talk). In Susanne Albers, editor, *17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands*, volume 162 of *LIPIcs*, pages 2:1-2:1. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.SWAT.2020.2.

[65] Ádám Timár. Finitely dependent random colorings of bounded degree graphs. *CoRR*, abs/2402.17068, 2024. doi:10.48550/arXiv.2402.17068.

[66] Joran van Apeldoorn and Tijn de Vos. A framework for distributed quantum queries in the CONGEST model. In Alessia Milani and Philipp Woelfel, editors, *PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022*, pages 109-119. ACM, 2022. doi:10.1145/3519270.3538413.

[67] ChengSheng Wang, Xudong Wu, and Penghui Yao. Complexity of eccentricities and all-pairs shortest paths in the quantum CONGEST model. *CoRR*, abs/2206.02766, 2022. doi:10.48550/ARXIV.2206.02766.

[68] Xudong Wu and Penghui Yao. Quantum complexity of weighted diameter and radius in CONGEST networks. In Alessia Milani and Philipp Woelfel, editors, *PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022*, pages 120-130. ACM, 2022. doi:10.1145/3519270.3538441.
# A Quantum, bounded-dependence, and non-signaling

This appendix introduces both the non-signaling model and the bounded-dependence model, which are the most powerful models that satisfy physical causality, and thus they generalize the quantum-LOCAL model. The distinction between the non-signaling model and the bounded-dependence depends on whether shared states are available (in the non-signaling model) or not (in the bounded-dependence model). We illustrate the difference between these models by analyzing the problem of $c = 2$-coloring a lifebuoy-shaped graph (see Fig. 6 and Fig. 7b) with locality $T = 2$.

We first introduce a circuit formalism which allows us to clarify the early works of Arfaoui and Fraigniaud [3], and Gavoille et al. [36], by re-expressing the randomized LOCAL and quantum-LOCAL models in this formalism (see Appendix A.1). Second, we introduce the concept of light-cones and the principle of non-signaling, explaining how (together with the symmetries of the graph) they define the non-signaling model (see Appendices A.1.3 and A.1.4). Third, we show in Appendix A.2 that lifebuoy-shaped graphs are not 2-colorable in the non-signaling model with locality $T = 2$ through a reduction from the 2-colorability of the cheating graph $H$ shown in Fig. 7a. At last, we define the bounded-dependence model based on our circuit formalism and on the following three principles: device replication; non-signaling and independence [14, 25, 26, 41]; and invariance under symmetries of the graph (see Appendix A.3). We stress its connection to the concept of finitely-dependent distributions [1, 44, 45, 47, 63].

<figure><img src="image_9.png" /><figcaption>Figure 6: An example of a *lifebuoy-shaped* graph $G$. The lifebuoy-shaped graphs are defined by the set $\mathcal{G}$ of graphs that are isomorphic to the above. Notice that their chromatic number is 2. In our case, the node labels required by the LOCAL model are unique and go from 1 to 12. Granting this extra power is not restrictive as we are proving a lower bound.</figcaption></figure>

## A.1 Randomized LOCAL, quantum-LOCAL, and non-signaling models

In the next two sections, we re-introduce the randomized LOCAL model and the quantum-LOCAL model for coloring lifebuoy-shaped graphs in a circuit formalism. This will later enable us to clarify the definitions of the non-signaling and bounded-dependence models.

### A.1.1 Randomized LOCAL model

We consider twelve nodes with unique identifiers ranging from 1 to 12 and that are connected in a lifebuoy-shaped graph that is a priori unknown to the nodes<fnref n="3" /> (an example of such graph is the labeled graph $G_0 \in \mathcal{G}$ illustrated in Fig. 7b). The nodes try to color this graph in the randomized

<footnote n="3">³A reader used to standard quantum nonlocality should see the graph — $H$ or $G \in \mathcal{G}$ — as an input of the problem, split and distributed among the local parties.</footnote>
<figure><img src="image_10.png" /><figcaption>(a) *H* has chromatic number 3.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) A distributed algorithm that finds a 2-coloring of the lifebuoy-shaped graphs $G \in \mathcal{G}$ would by definition 2-color the particular instance $G = G_0$.</figcaption></figure>

Figure 7: The joint view of the couple of nodes $u, v = 1, 2$ after $T = 2$ rounds of communication is limited to the gray area. In this region the graphs $G_0$ and $H$ are identical. The non-signaling principle implies that the outputs $(c_1, c_2)$ must therefore be identically distributed in both $G_0$ and $H$.

**LOCAL** model within $T = 2$ steps of synchronous communication. The difficulty is that a given node ignore which $G \in \mathcal{G}$ connects the set of labelled nodes: it can only discover a local part of the structure of $G$ by communicating to its neighbors. The most general ($T = 2$)-round strategy for the node 1 consists of the following procedure, which alternates between randomized processing steps and communication steps (the computational power and size of exchanged messages are unbounded):

**Processing 0:** Sample a random real number and store it locally.

**Communication 1:** Send all stored information, including the sampled random number, to all neighbors. Receive information from all neighbors and store it for subsequent rounds (in $G_0$, the neighbors are 2, 3, 5).

**Processing 1:** Process all stored information (possibly in a randomized way) and store the result.<fnref n="4" />

**Communication 2:** Send all stored information, including all received messages and the outputs of processing steps, to all neighbors. Receive information from neighbors and store it.

**Processing 2:** Process all stored information (possibly in a randomized way) to output a color.

Such $T$-round strategy on the graph $G$ can be represented formally as a circuit $C_{G,T}$, such as in Fig. 8a where semicircles, line wires, and squares respectively represent the sampling of a random number, the transfer (or storage) of information, and the processing of information. Once the concrete operations performed by the nodes (i.e. randomness sampling and processing) are made explicit, it is possible to compute (using classical information theory) the exact output distribution of the strategy on graph $G$, that is, the probability distribution $\text{Pr}[c_1, \dots, c_n \mid C_{G,T}]$ of observing that the set of nodes $\{1, \dots, n\}$ outputs the colors $\{c_1, \dots, c_n\}$ when connected as per one of the lifebuoy-shaped graphs $G \in \mathcal{G}$. Importantly, in our model, the operations performed by the nodes cannot depend on the connection graph $G$.

<footnote n="4">⁴In classical information theory, it is known that intermediate processing gates can be taken as identity gates, that is, any strategy can be simulated by a two-layer circuit where the parties send their first random number to all parties up to a distance $T$, and then make a unique processing step after all the communication has taken place. In quantum and non-signaling theories, this is not the case anymore [28].</footnote>
A generic classical strategy with shared randomness can be in the same way represented by the general circuit of Fig. 8b, by initializing the circuit with a source of randomness common to all nodes (the large semicircle).

### A.1.2 Quantum-LOCAL model

Any quantum strategy can also be represented by the circuit formalism of Fig. 8 by using resources and processing operations that are quantum rather than classical. Quantum information theory provides a concrete mathematical formalism (based on the tensor product of Hilbert spaces) with rules to represent the potential operations performed by each of the gates of the circuit. Semicircles, line wires, and squares now respectively represent the creation of a quantum state (a density matrix), the transfer (or storage) of quantum information, and the processing of quantum information with quantum channels (or quantum measurements in the last layer) represented by completely positive operators. Once the quantum states and channels are made explicit, the Born rule of quantum information theory [15, 58] allows computing $\text{Pr}[c_1, \dots, c_n | C_{G,T}]$, the output distribution of the strategy on graph $G$.

However, analyzing the quantum-LOCAL model directly is complicated. Instead, we employ the fact that it is possible to bound the time complexity of the quantum-LOCAL model by analyzing models that do not depend on the mathematical formalism of quantum information theory (and which are, therefore, arguably simpler). In the present appendix, we utilize the fact that quantum-LOCAL is sandwiched between the randomized LOCAL model (less powerful) and the non-signaling model (the most powerful model satisfying the information-theoretic principles of non-signaling, independence and device replication we introduce below). We next introduce the non-signaling model.

### A.1.3 The non-signaling model (with unique identifiers)

The non-signaling model is the most powerful model of synchronous distributed computing that does not violate physical causality, when a pre-established shared resource exists.

The formulation of the non-signaling model is radically different from the randomized LOCAL and quantum-LOCAL models. The randomized LOCAL and quantum-LOCAL models are based on classical (randomized) and quantum information theory which both provide a mathematical formalism to describe information processing gates and to compute the probability distribution of outputs when these gates are placed in a circuit. To show that some probability distribution is feasible in these models, one needs to propose a valid strategy in these mathematical formalisms. The non-signaling model does not rely on any underlying mathematical formalism, but on some information-theoretical principles which should not be violated. More precisely, to show that some probability distribution is feasible in the non-signaling model, one needs to explain how to obtain it, but only to make sure that this probability distribution is compatible with the *non-signaling* principle in a way we now explain.

Before introducing this principle, we state the following definition of light-cones:

**Definition A.1 (Past light-cone).** Consider a circuit. Consider a subset of gates $R$, and another gate $s \notin R$ in that circuit. We say that $s$ is in the past light-cone of $R$ if starting from $s$, one can reach a gate in $R$ by traveling down the circuit. For instance, in Fig. 8b, the past light-cone of the second processing gates of nodes $\{1, 2\}$ is composed of all gates in red.

**Remark A.2.** Light-cones allow to formalize the fact that, in a circuit, the precise time ordering in which the gates process information has no influence over the result, as long as physical causality (that is, information can be transferred only through communication) is preserved. For instance, in
<figure><img src="image_12.png" /><figcaption>(a) Circuit representation of a non-signaling strategy on graph $G_0$ of Fig. 7b, without a shared resource. Note the cyclicity of the circuit. Highlighted in red is the past-light-cone of the joint output $(c_1, c_2)$, that is the set of gates which connects to the output gates producing $(c_1, c_2)$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Circuit representation of a non-signaling strategy on graph $G_0$ of Fig. 7b, with an arbitrary shared resource. The joint output $(c_1, c_2)$ remain, after $T = 2$ rounds of communication, independent of the graph structure around nodes 11 and 12, because the difference lies outside their joint past light-cones.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(c) Circuit representation of a non-signaling strategy on graph $H$ of Fig. 7a, with an arbitrary shared resource. Note the difference between this circuit and the one of Fig. 8b (namely, the different connections between the top layer and bottom layer of the circuit) is only manifested outside the joint past light-cone of the outputs $(c_1, c_2)$.</figcaption></figure>

Figure 8: The above circuits represent non-signaling strategies (it includes as special cases the classical strategies and quantum strategies) executed by the nodes 1 and 2 in various scenarios. The semicircles represent private (Fig. 8a) or shared (Fig. 8b and Fig. 8c) arbitrary-but-non-signaling resources; the wires depict communication (or storage), and the squares are local operations (using possibly private resources). The last layer of gates (or measurements) outputs the individual colors of the nodes (i.e. classical variables). Since the nodes start with no knowledge about the identity of their neighbors, the operations of the gates are a priori independent of the graph structure (as long as the nodes have the right degree). For the special cases of classical and quantum strategies, the output distribution can be computed directly from those circuits, which define it uniquely.
Fig. 8a, our drawing of the circuit represents the processing-1 gate of node 8 as being in the past of the processing-2 gate of node 2. However, by stretching the communication lines, another drawing in which this time ordering is exchanged exists, and this is possible as long as one node is not in the past light cone of another. The name “light-cone” refers to relativity, where physical causality is bounded by the speed of light. Circuits provide an abstracted representation of physical causality that is not based on any notion of spacetime.

We now state the non-signaling principle<fnref n="5" />, which is essentially the only constraint in the non-signaling model.

**Definition A.3 (Non-signaling principle).** Consider a set of gates, two different circuits C, C' connecting them, and corresponding distributions Pr[c₁, ..., cₙ | C], Pr[c₁, ..., cₙ | C']. Let U be a subset of measurement gates whose past light-cones in C and C' coincide (i.e. they are composed of the same gates which are connected in the same way). Then Pr[{cᵢ}ᵢ∈U | C] = Pr[{cᵢ}ᵢ∈U | C'].

Implicitly, a non-signaling theory assumes that, given a set of gates and a valid way to connect them in a circuit C, one obtains a corresponding distribution Pr[c₁, ..., cₙ | C]<fnref n="6" /> (here the alphabet of the outputs cᵢ is not limited: e.g., in case of unexpected circuits, the measurement gates can produce failure outputs).

We are now ready to define the non-signaling model, which is associated to circuits with a pre-shared non-signaling resource such as in Fig. 8b:

**Definition A.4 (Non-signaling model, with unique identifiers).** The distribution

$$ \Pr[c_1, \dots, c_n | C_{G,T}] $$

is feasible in the non-signaling model (with unique identifiers) with locality T on graph G if and only if, for all possible alternative connecting graphs H of the nodes, there exists a distribution P = Pr[c₁, ..., cₙ | C_{H,T}] such that the no-signaling principle is respected.<fnref n="7" />

Note that H might not be a lifebuoy-shaped graph: in the case a gate ‘discovers’ this unexpected situation, it has the possibility to produce a new output from a set of error outputs (i.e. it crashes and no further useful constraint can be derived).

### A.1.4 The non-signaling model without unique identifiers

We have up until now considered N = 12 nodes with unique identifiers ranging from 1 to N = 12. When the nodes do not start with unique identifiers, the situation is slightly more complicated. In that case, the resulting distribution should be invariant under subgraph isomorphism, as all nodes are running identical programs and the circuit is thus completely symmetric under permutations of nodes<fnref n="8" />. For instance, if the nodes were to color the graph of Fig. 7b without being a priori assigned

<footnote n="5">⁵Chiribella and Spekkens [24] call this principle *no-signaling from the future*.</footnote>

<footnote n="6">⁶Note that the gates have “types” and can only be connected to other gates of matching types: For instance, in our case, the inputs of gates from the second processing step must correspond to the outputs of gates from the first processing step. The theory of circuits can be formalized using category theory — see, e.g. [31].</footnote>

<footnote n="7">⁷Note that considering scenarios with more than one copies of each node does not allow us to derive additional constraints, since the pre-shared non-signaling resource cannot by definition be cloned and extended to more than one copy of each of its original recipient.</footnote>

<footnote n="8">⁸Note that while a shared classical resource is inherently symmetric, because it can be without a loss of generality taken to be distributed identically to each party, a non-signaling resource is not a priori symmetric under permutation of the parties that it connects. The absence of identifiers thus forces the non-signaling model to pre-share only a subset of all possible non-signaling resources, namely the subset that respects such symmetry.</footnote>
unique identifiers, the resulting circuit $C_{G,T}$ would have some symmetries (as all processing gates would be the same in any layer of the respective steps 0, 1 and 2), implying that the distribution should be invariant by several non-trivial graph isomorphisms cyclically permuting the nodes, or inverting the inner and outer cycle of 6 nodes.

**Definition A.5** (Non-signaling model, without unique identifiers). The distribution

$$ \Pr[c_1, \dots, c_n | C_{G,T}] $$

is feasible in the non-signaling model (without unique identifiers) in $T$ communication steps on graph $G$ if and only if the following two conditions are respected: for all possible alternative connecting graphs $H$ of the nodes, there exists a distribution $P = \Pr[c_1, \dots, c_n | C_{H,T}]$ such that the no-signaling principle is respected; and the distributions in $G$ and $H$ are invariant under subgraph isomorphism.

This definition can also be generalized to the case where several nodes with the same identifiers are present in $G$, or were the number of identifiers ranges from 1 to $M \neq N$.

## A.2 Graph $G$ is not 2-colorable in $T = 2$ rounds

We now show by contradiction that the nodes 1, ..., 12 cannot 2-color the set $G$ of lifebuoy-shaped graphs with a non-signaling strategy (including pre-shared non-signaling resources) in $T = 2$ rounds of communication. More precisely, we prove that if there existed such a non-signaling algorithm able to color any $G \in G$, then the same algorithm would also color the cheating graph $H$ with 2 colors, which is impossible.

*Proof.* Assume by contradiction that there exists such a non-signaling algorithm, that is, there exist gates as in Fig. 8b such that the resulting probability distribution $\Pr[c_1, \dots, c_{12} | C_{G,T}]$ is a proper coloring for all lifebuoy-shaped graphs $G \in G$. Such proper coloring means that for all $G \in G$, and for all nodes $u, v$ that are neighbors in $G$, it holds that $\Pr[c_u \neq c_v | C_{G,T}] = 1$.

We consider the same nodes performing the same gates, but we change the edges so that the connected nodes now form the graph $H$ in Fig. 7b. Let $\Pr[c_1, \dots, c_{12} | C_{H,T}]$ be the distribution of output colors in that new configuration<fnref n="9" />. Consider two nodes connected by an edge in $H$: by symmetry of $H$, we can without a loss of generality assume that these are nodes 1 and 2. We introduce the lifebuoy-shaped graph $G_0$ of Fig. 7b ($G_0 \in G$ depends on our choice of nodes, here 1, 2, in $H$). Then, we observe that the common past light-cones of the two nodes is the same when connected through $H$ or through $G_0$ (compare the circuit of Fig. 8b with the circuit of Fig. 8c). It hence holds that $\Pr[c_1 \neq c_2 | C_{H,T}] = 1 = \Pr[c_1 \neq c_2 | C_{G_0,T}]$ due to the non-signaling principle. We conclude that the non-signaling distributed algorithm outputs a 2-coloring for $H$, which is impossible. □

## A.3 Bounded-dependence model

The bounded-dependence model is similar to the non-signaling model, but the former does not allow pre-shared non-signaling resources between the nodes. The following two new principles are needed to define feasible distributions in the bounded-dependence model.

<footnote n="9">⁹While we are deceiving the nodes by promising a lifebuoy-shaped connecting graph but imposing instead $H$, the nodes cannot locally detect the fraud in $T = 2$ communication steps or less. (More formally, the past light-cone in $H$ of any node is then compatible with a lifebuoy-shaped graph — an individual node cannot detect the difference and must therefore, according to the non-signaling principle, output a color as if it were in a lifebuoy-shaped graph.)</footnote>
<figure><img src="image_15.png" /><figcaption>Figure 9: In the bounded-dependence model, one can find non-trivial subgraph isomorphisms even when the nodes are provided with unique identifiers.</figcaption></figure>

**Definition A.6 (Independence principle).** Consider a set of gates connected in a circuit C, and the corresponding distribution $Pr[c_1, ..., c_n | C]$. Let U, V be two subsets of measurement gates producing the outputs {$c_u$}$_{u \in U}$ and {$c_v$}$_{v \in V}$, respectively. If the past light-cones of U and V do not intersect, then $Pr[{c_w}]{w \in U \cup V | C} = Pr[{c_u}]{u \in U | C} \cdot Pr[{c_v}]{v \in V | C}$, that is their output distributions are independent.

**Definition A.7 (Device-replication principle).** Identical and independent copies of non-signaling gates and non-signaling resources can be prepared<fnref n="10" />.

Then, we obtain the following definition:

**Definition A.8 (Bounded-dependence model, with unique identifiers).** The distribution

$$Pr[c_1, ..., c_n | C_{G,T}]$$

with unique identifiers has *bounded dependence* with locality T on graph G (without pre-shared non-signaling resources) if and only if for all possible alternative connecting graph H of the nodes and their replicates, there exists a distribution $Pr[c_1, ..., c_m | C_{H,T}]$ such as the non-signaling and independence principles are respected, and such that the distribution is invariant under subgraph isomorphisms.

Note a subtlety related to subgraph isomorphisms in the bounded-dependence model. There is the variant where the nodes have identifiers in G, and the one where they do not. When the nodes do not have any identifiers, the class of subgraph isomorphisms of all alternative graphs H created out of the nodes in G and their replicates is obviously larger than with identifiers, because the subgraph isomorphisms must respect the identifiers. However, even if the nodes of G do have distinct identifiers, as H is created out of possibly many copies of the original nodes of G, H might contain several nodes with the same identifiers. Hence, the group of subgraph isomorphism of H might be nontrivial even if all nodes in G have distinct identifiers. For instance, in lifebuoy-shaped graphs, one could consider the case represented in Fig. 9, which starts from the graph $G_0$ in Fig. 7b, duplicates all nodes, and constructs a new graph H of 24 nodes with identifiers ranging from 1 to 12 with one non-trivial graph isomorphism cyclically permuting the nodes.

<footnote n="10">¹⁰Note that this principle does not imply that one can duplicate *unknown* non-signaling resources: device-replication compatible with the quantum no-cloning theorem.</footnote>
### A.3.1 Relation with finitely-dependent distributions

Our bounded-dependence model is directly connected to the concept of finitely-dependent distributions introduced in mathematics [1, 44–47, 63]. In this framework, in a graph $H$, the color $c_i$ produced by each node $i$ is seen as the result of a random process $C_i$. The set of all random processes $\{C_i\}_i$ is said to be $k$-dependent in graph $H$ if, for any two subsets $U, V$ of the nodes of $H$ which are at least at distance $k+1$, the two sets of processes $\{C_u\}_{u \in U}$ and $C_{v \in V}$ are independent. In our notation, assuming even $k$ and taking $T = k/2$, this is equivalent to asking that $\Pr[\{c_w\}_{w \in U \cup V} | C_{H,T}] = \Pr[\{c_u\}_{u \in U} | C] \cdot \Pr[\{c_v\}_{v \in V} | C_{H,T}]$.

Hence, the question of the existence of distributions with bounded dependence that solve some problem can directly be formulated in terms of the existence of finitely dependent distributions over a family of graphs that satisfy additional constraints of compatibility (to satisfy the non-signaling principle) and symmetries (to cope with subgraph isomorphisms).
<figure><img src="image_16.png" /><figcaption>Figure 10: Landscape of models and their relations for LCL problems. A black arrow $X \to Y$ indicates that model $Y$ is at least as strong as model $X$ and can simulate any algorithm designed there. A blue arrow $X \to Y$ indicates that we additionally get symmetry-breaking for free: locality $O(\log^* n)$ in model $X$ implies locality $O(1)$ in model $Y$. An orange arrow $X \to Y$ indicates that at least in rooted trees we can simulate highly-localized algorithms in model $X$ using the weaker model $Y$ so that e.g. locality $O(\log^* n)$ in model $X$ implies locality $O(\log^* n)$ in model $Y$ (see Theorem 7.1 and [38] for details).</figcaption></figure>