Found 48 Documents (Results 1–48)
Distributed half-integral matching and beyond. (English) Zbl 07809116
MSC:
68Qxx
Distributed half-integral matching and beyond. (English) Zbl 07786526
Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 339-356 (2023).
The landscape of distributed complexities on trees and beyond. (English) Zbl 07824245
Milani, Alessia (ed.) et al., Proceedings of the 41st ACM symposium on principles of distributed computing, PODC ’22, Salerno, Italy, July 25–29, 2022. New York, NY: Association for Computing Machinery (ACM). 37-47 (2022).
Node and edge averaged complexities of local graph problems. (English) Zbl 07824242
Milani, Alessia (ed.) et al., Proceedings of the 41st ACM symposium on principles of distributed computing, PODC ’22, Salerno, Italy, July 25–29, 2022. New York, NY: Association for Computing Machinery (ACM). 4-14 (2022).
Distributed \(\Delta\)-coloring plays hide-and-seek. (English) Zbl 07774353
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 464-477 (2022).
MSC:
68Qxx
Near-optimal distributed degree+1 coloring. (English) Zbl 07774352
Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 450-463 (2022).
MSC:
68Qxx
Linial for lists. (English) Zbl 1522.68734
Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. (English) Zbl 07824207
Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 283-293 (2021).
Locally checkable problems in rooted trees. (English) Zbl 07824205
Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 263-272 (2021).
Can we break symmetry with \(o(m)\) communication? (English) Zbl 07824203
Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 247-257 (2021).
Improved distributed approximations for maximum independent set. (English) Zbl 1540.68188
Attiya, Hagit (ed.), 34th international symposium on distributed computing, DISC 2020, virtual conference, October 12–16, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 179, Article 35, 16 p. (2020).
Classification of distributed binary labeling problems. (English) Zbl 1540.68164
Attiya, Hagit (ed.), 34th international symposium on distributed computing, DISC 2020, virtual conference, October 12–16, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 179, Article 17, 17 p. (2020).
Local conflict coloring revisited: Linial for lists. (English) Zbl 1540.68308
Attiya, Hagit (ed.), 34th international symposium on distributed computing, DISC 2020, virtual conference, October 12–16, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 179, Article 16, 18 p. (2020).
Brief announcement: Round eliminator: a tool for automatic speedup simulation. (English) Zbl 07323209
Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 352-354 (2020).
How much does randomness help with locally checkable problems? (English) Zbl 07323203
Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 299-308 (2020).
Seeing far vs. seeing wide: volume complexity of local graph problems. (English) Zbl 07323174
Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 89-98 (2020).
Truly tight-in-\(\Delta\) bounds for bipartite maximal matching and variants. (English) Zbl 07323172
Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 69-78 (2020).
Fooling views: a new lower bound technique for distributed computations under congestion. (English) Zbl 1497.68556
Hardness of minimal symmetry breaking in distributed computing. (English) Zbl 07298699
Nowak, Thomas (ed.), Proceedings of the 38th ACM symposium on principles of distributed computing, PODC ’19, Toronto, ON, Canada, July 29 – August 2, 2019. New York, NY: Association for Computing Machinery (ACM). 369-378 (2019).
The distributed complexity of locally checkable problems on paths is decidable. (English) Zbl 07298685
Nowak, Thomas (ed.), Proceedings of the 38th ACM symposium on principles of distributed computing, PODC ’19, Toronto, ON, Canada, July 29 – August 2, 2019. New York, NY: Association for Computing Machinery (ACM). 262-271 (2019).
Locality of not-so-weak coloring. (English) Zbl 1534.68138
Censor-Hillel, Keren (ed.) et al., Structural information and communication complexity. 26th international colloquium, SIROCCO 2019, L’Aquila, Italy, July 1–4, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11639, 37-51 (2019).
Localisation-resistant random words with small alphabets. (English) Zbl 1436.68280
Mercaş, Robert (ed.) et al., Combinatorics on words. 12th international conference, WORDS 2019, Loughborough, UK, September 9–13, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11682, 193-206 (2019).
An exponential separation between randomized and deterministic complexity in the LOCAL model. (English) Zbl 1404.05203
On the probe complexity of local computation algorithms. (English) Zbl 1499.68381
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 50, 14 p. (2018).
An optimal distributed \((\Delta+1)\)-coloring algorithm? (English) Zbl 1427.68355
Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 445-456 (2018).
Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model. (English) Zbl 1373.68258
Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 195-197 (2016).
A lower bound for the distributed Lovász local lemma. (English) Zbl 1375.68191
Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 479-488 (2016).
Finitely dependent coloring. (English) Zbl 1361.60025
Exact bounds for distributed graph colouring. (English) Zbl 1471.68323
Scheideler, Christian (ed.), Structural information and communication complexity. 22nd international colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015. Post-proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9439, 46-60 (2015).
Optimal deterministic routing and sorting on the congested clique. (English) Zbl 1323.68034
Proceedings of the 2013 ACM symposium on principles of distributed computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2065-8). 42-50 (2013).
Distributed minimum dominating set approximations in restricted families of graphs. (English) Zbl 1271.68070
MIS on trees. (English) Zbl 1321.68482
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC ’11, San Jose, CA, USA, June 06–08, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0719-2). 41-48 (2011).
Distributed computing with advice: information sensitivity of graph coloring. (English) Zbl 1267.05118
Leveraging Linial’s locality limit. (English) Zbl 1161.68344
Taubenfeld, Gadi (ed.), Distributed computing. 22nd international symposium, DISC 2008, Arcachon, France, September 22–24, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87778-3/pbk). Lecture Notes in Computer Science 5218, 394-407 (2008).
A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. (English) Zbl 1283.68398
Proceedings of the 26th annual ACM symposium on principles of distributed computing, PODC ’07, Portland, OR, USA, August 12–15, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-616-5). 53-60 (2007).
A faster distributed algorithm for computing maximal matchings deterministically. (English) Zbl 1321.68469
Proceedings of the 18th annual ACM symposium on principles of distributed computing, PODC ’99, Atlanta, GA, USA, May 3–6, 1999. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-099-6). 219-228 (1999).
Filter Results by …
Document Type
- Journal Articles (19)
- Collection Articles (29)
all
top 5
Author
- Olivetti, Dennis (14)
- Suomela, Jukka (13)
- Balliu, Alkida (12)
- Brandt, Sebastian F. (11)
- Chang, Yi-Jun (7)
- Lenzen, Christoph (6)
- Hirvonen, Juho (5)
- Kuhn, Fabian (5)
- Pettie, Seth (5)
- Maus, Yannic (3)
- Rybicki, Joel (3)
- Tonoyan, Tigran (3)
- Wattenhofer, Roger P. (3)
- Dahal, Sameep (2)
- Fraigniaud, Pierre (2)
- Gavoille, Cyril (2)
- Ghaffari, Mohsen (2)
- Holroyd, Alexander E. (2)
- Khoury, Seri (2)
- Kopelowitz, Tsvi (2)
- Li, Wenzheng (2)
- Studený, Jan (2)
- Tereshchenko, Aleksandr (2)
- Abboud, Amir (1)
- Censor-Hillel, Keren (1)
- Efron, Yuval (1)
- Feige, Uriel (1)
- Feuilloley, Laurent (1)
- Fischer, Orr (1)
- Gfeller, Beat (1)
- Göös, Mika (1)
- Grunau, Christoph (1)
- Halldórsson, Magnús Mar (1)
- Hańćkowiak, Michał (1)
- Hutchcroft, Tom (1)
- Ilcinkas, David (1)
- Kachigar, Ghazal (1)
- Karoński, Michał (1)
- Kawarabayashi, Ken-ichi (1)
- Keller, Barbara (1)
- Korman, Amos (1)
- Lempiäinen, Tuomo (1)
- Levy, Avi (1)
- Liggett, Thomas Milton (1)
- Linial, Nathan (1)
- Nolin, Alexandre (1)
- Pai, Shreyas (1)
- Panconesi, Alessandro (1)
- Pandurangan, Gopal (1)
- Parter, Merav (1)
- Patt-Shamir, Boaz (1)
- Pelc, Andrzej (1)
- Peleg, David (1)
- Pemmaraju, Sriram V. (1)
- Pignolet, Yvonne-Anne (1)
- Rabie, Mikaël (1)
- Robinson, Peter (1)
- Rosenbaum, Will (1)
- Rozhoň, Václav (1)
- Schild, Aaron (1)
- Schmid, Stefan (1)
- Schwartzman, Gregory (1)
- Spinka, Yinon (1)
- Uitto, Jara (1)
- Vardi, Shai (1)
- Vicari, Elias (1)
- Zémor, Gilles (1)
all
top 5
Serial
- Distrib. Comput. (7)
- SIAM J. Comput. (4)
- Ann. Probab. (2)
- Theor. Comput. Sci. (2)
- Comb. Probab. Comput. (1)
- Electron. J. Comb. (1)
- Electron. Commun. Probab. (1)
- Forum Math. Pi (1)
