Invitation to Local Algorithms

Václav Rozhoň

Type: Preprint

Publication Date: 2024-06-27

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2406.19430

Abstract

This text provides an introduction to the field of distributed local algorithms -- an area at the intersection of theoretical computer science and discrete mathematics. We collect many recent results in the area and demonstrate how they lead to a clean theory. We also discuss many connections of local algorithms to areas such as parallel, distributed, and sublinear algorithms, or descriptive combinatorics.

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Converting Online Algorithms to Local Computation Algorithms	2012	Yishay Mansour Aviad Rubinstein Shai Vardi Ning Xie
+	Space-efficient Local Computation Algorithms	2011	Noga Alon Ronitt Rubinfeld Shai Vardi Ning Xie
+	Aspects of the theory of local algorithms on graphs	1973	I. V. Khutoryanskaya
+	Space-efficient Local Computation Algorithms	2012	Noga Alon Ronitt Rubinfeld Shai Vardi Ning Xie
+	New techniques and tighter bounds for local computation algorithms	2016	Omer Reingold Shai Vardi
+	New Classes of Distributed Time Complexity	2017	Alkida Balliu Juho Hirvonen Janne H. Korhonen Tuomo Lempiäinen Dennis Olivetti Jukka Suomela
+	New Classes of Distributed Time Complexity	2017	Alkida Balliu Juho Hirvonen Janne H. Korhonen Tuomo Lempiäinen Dennis Olivetti Jukka Suomela
+	Local Computation Algorithms for the Lovász Local Lemma	2018	Dimitris Achlioptas Themis Gouleakis Fotis Iliopoulos
+ PDF Chat	New classes of distributed time complexity	2018	Alkida Balliu Juho Hirvonen Janne H. Korhonen Tuomo Lempiäinen Dennis Olivetti Jukka Suomela
+ PDF Chat	Derandomizing local distributed algorithms under bandwidth restrictions	2020	Keren Censor-Hillel Merav Parter Gregory Schwartzman
+	On Derandomizing Local Distributed Algorithms	2017	Mohsen Ghaffari David G. Harris Fabian Kühn
+ PDF Chat	Lower bounds for local approximation	2012	Mika Göös Juho Hirvonen Jukka Suomela
+	Algorithms and Generalizations for the Lovasz Local Lemma	2015	David G. Harris
+	Almost Global Problems in the LOCAL Model	2018	Alkida Balliu Sebastian Brandt Dennis Olivetti Jukka Suomela
+	On the Complexity of Local Distributed Graph Problems	2016	Mohsen Ghaffari Fabian Kühn Yannic Maus
+ PDF Chat	Limits of local algorithms over sparse random graphs	2014	David Gamarnik Madhu Sudan
+	Fast Local Computation Algorithms	2011	Ronitt Rubinfeld Gil Tamir Shai Vardi Ning Xie
+	Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees	2022	Sebastian Brandt Yi‐Jun Chang Jan Grebík Christoph Grunau Václav Rozhoň Zoltán Vidnyánszky
+	International seminar algorithms and combinatorics	1979
+	An improvement of the Moser-Tardos algorithmic local lemma	2011	Wesley Pegden

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors