Local Complexity: New Results and Bridges to Other Fields

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.