COLLOQUIUM AT BAR-ILAN UNIV. COMPUTER SCIENCE DEPART. - ORR FISCHER - Monday, January 27th 2025, at 12:00 - SEMINAR ROOM 226
WHO: Dr. Orr Fischer, Bar-Ilan University
WHEN: Monday, January 27th 2025 at 12:00
WHERE: BUILDING 503 (Computer Science) SEMINAR ROOM 226
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 we have no prior knowledge of, other than some given training examples randomly taken from a distribution. We are hence required to extrapolate from the local (our training set), to the global (any new sample). We study comparative-based queries - queries which compare the similarity of different pairs of elements. In the course of this line of works, we obtained new insights into the k-nearest neighbor problem, surprisingly through techniques developed for distributed computing.
Bio:
Orr Fischer conducted his PhD studies at Tel-Aviv University under the guidance of Prof. Rotem Oshman, focusing on distributed computing, sublinear algorithms, and communication complexity. Later, he joined as a postdoctoral fellow at Weizmann Institute of Science at Prof. Merav Parter lab, and researched distributed computing under byzantine settings, as well as PAC learning settings. Today, he is a postdoctoral fellow at the Bar-Ilan University, hosted by Dr. Talya Eden, Dr. Arnold Filtser, and Prof. Ester Ezra. Orr has received several accolades for his work, including best paper awards at DISC and SIROCCO, as well as the Deutch award for excellence in research, and the Weizmann Faculty postdoctoral excellence fellowship.
