Technical Report MSC-2020-21

TR#:MSC-2020-21
Class:MSC
Title: New Advances in Distributed Optimization and Distance Computation
Authors: Yuval Efron
Supervisors: Keren Censor-Hillel
PDFMSC-2020-21.pdf
Abstract: This thesis studies fundamental optimization and distance computation problems in the distributed CONGEST model of computation. The contributions include both upper and lower bounds. The first part of the thesis focuses on lower bounds for optimization, for which we employ the well known 2-party communication complexity framework. In addition to providing new near quadratic lower bounds for minimum dominating set and weighted max cut, our contributions include a novel connection between error correcting codes and lower bounds for CONGEST. We introduce a new gadget, called code gadget, that incorporates error correcting codes into a family of hard graphs. With this family of hard graphs we are able to prove the first near quadratic lower bound for approximating an optimization problem, namely, maximum independent set, by a constant multiplicative factor in CONGEST.

The second original technical contribution of the first part of this thesis is the first application of multi-party communication complexity for proving lower bounds for the CONGEST model. The only previous application of multi-party communication complexity to show lower bounds for the distributed setting was for the Broadcast Congested Clique model. In this thesis, we employ the multi-party setting to amplify the aforementioned hardness of approximation result for maximum independent set.

The second part of this thesis focuses on distance computations, specifically on the fundamental parameters of diameter, radius and eccentricities. As allowing approximate solutions enables one to beat lower bounds for exact computation, we focus on approximate computation of these parameters. In particular, we focus on the weighted and directed variants of these parameters. We give a nearly full characterization of the trade-off between the approximation ratio and the round complexity of computing approximations to the variants we consider. Furthermore, motivated by applications in computational geometry and recent work in the sequential setting, we bring to light the study of bi-chromatic diameter and radius into the CONGEST model. We provide the first upper and lower bound results for these variants in the distributed setting. On the technical side, we introduce a generalization of the notion of pseudo-center, which was introduced in recent work, and present an efficient way to compute it. Furthermore, our lower bound constructions incorporate the usage of previously unused functions in the 2-party communication complexity framework.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information
DisclaimerRecent theses may have not yet been approved by the Technion Senate, and are provided here for the purpose of fast dissemination of knowledge only. Final approval of the Technion Senate is needed for a thesis to be used for the partial fulfillment of the requirements for the degree of M.Sc. or Ph.D.

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2020/MSC/MSC-2020-21), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2020
To the main CS technical reports page

Computer science department, Technion
admin