Technical Report MSC-2018-24

Title: New Lower Bounds for the CONGEST Model
Authors: Seri Khoury
Supervisors: Keren Censor-Hillel
PDFCurrently accessibly only within the Technion network
Abstract: In this thesis we study the CONGEST model of distributed computing. We focus on proving lower bounds for solving fundamental graph problems for this model. In the first part of this thesis, we investigate the framework of reductions from two-party communication problems, which is a well known technique for proving lower bounds for distributed computing. We present a new gadget for this framework which we refer to as the bit-gadget. The contribution of the bit-gadget is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs.

Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. All of the above are optimal up to logarithmic factors.

Unfortunately, the two-party communication framework is provably incapable of providing any lower bounds for some fundamental graph problems, such as triangle detection and finding a maximal independent set. Nevertheless, in the second part of this thesis we study a new technique, which we refer to as the Fooling Views technique. We use this technique together with extremal graph combinatorics to prove the first lower bound for triangle detection for the CONGEST model.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, 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 2018
To the main CS technical reports page

Computer science department, Technion