Open access
Autor(in)
Datum
2024Typ
- Doctoral Thesis
ETH Bibliographie
yes
Altmetrics
Abstract
This thesis presents new results for the theory of local complexity in distributed computation and builds bridges to other areas of theoretical computer science and discrete mathematics, such as parallel, distributed, and sublinear algorithms, descriptive combinatorics, and finitary factors.
We begin the thesis with an extended introduction to the area of local algorithms, particularly focusing on recent complexity-theoretic developments. We hope this text could serve as a useful resource for a broader audience, especially newcomers to the field and researchers in adjacent areas.
Next, the thesis presents our new technical results in two parts. The first part contributes to our understanding of the possible complexities of local problems. Specifically, we classify the complexities of local problems on concrete graph families, with a focus on trees and grids. We also present new algorithms for fundamental problems, such as network decomposition and the Lovász local lemma.
The second part of the thesis builds and explores connections from local complexity to other fields: We apply techniques from local algorithms to classify the complexities of problems in the local computation model of sublinear algorithms. We extend local algorithms for network decompositions to weighted graphs, leading to new parallel and distributed algorithms for several graph problems. Finally, we explore the connection between local algorithms, descriptive combinatorics, and finitary factors, yielding new results in these fields. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000699789Publikationsstatus
publishedExterne Links
Printexemplar via ETH-Bibliothek suchen
Beteiligte
Referent: Steger, Angelika
Referent: Bernshteyn, Anton
Referent: Ghaffari, Mohsen
Referent: Haeupler, Bernhard
Referent: Pettie, Seth
Verlag
ETH ZurichThema
Computer scienceOrganisationseinheit
03672 - Steger, Angelika / Steger, Angelika
ETH Bibliographie
yes
Altmetrics