Orr Fischer (Bar Ilan University) – A Global View of Locality Through the Lens of Distributed Computing, Parallel Computing, and Learning Theory

Title: A Global View of Locality Through the Lens of Distributed Computing, Parallel Computing, and Learning Theory

Abstract:
Locality, i.e. computing under partial knowledge, is a fundamental challenge that can manifest itself in many versatile ways: from a distributed network where each processor has to rely on local information to solve global tasks (such as routing), to a sublinear algorithm that only has access to a small fraction of the input before outputting some estimate or approximate solution. In this talk, I will highlight the many faces of this challenge in the distributed, parallel, and learning settings.

– Distributed settings: CONGEST is a distributed model which aims to capture both locality and communication limitations. I will present several results for this model, which highlight the interplay of the two limitations, and in particular the subgraph freeness problem – a very local problem that requires a surprisingly global solution. Additionally, I will discuss how to overcome challenges arising from the inclusion of other considerations, such as security, and resilience to crashes and corruptions.

– Parallel settings: The widely adopted Map-Reduce Framework revolutionized parallel computation in the industry, and has been the focus of much theoretical research. The Massively-parallel computation model (MPC) is one such avenue to explore this framework. I will discuss several results in the MPC model, and in particular an interesting new research direction, in which we show that even a single machine with a slightly more global view is sufficient to overcome many of the known lower bounds for this setting. At the heart of our techniques are sampling lemmas designed to connect small but informative parts of the input (e.g. random subgraphs if the input is a graph) to global properties of the input.

– Learning Theory: In the PAC learning setting, we would like to be able to answer queries about a set of data elements, given only a few training examples randomly taken from a distribution. Through techniques developed for the study of locality and graph theory, we are able to give new insights into various problems of interest, such as the sample complexity of contrastive learning and hierarchical clustering, and also obtain insights to the k nearest neighbors problem.