Technical Report PHD-2017-08

Title: Algorithms for Environments with Uncertainty
Authors: Gregory Schwartzman
Supervisors: Keren Censor-Hillel
Abstract: In this research we study computation in environments with uncertainty, specifically, the distributed and streaming environments. We adapt the local-ratio technique to the distributed and streaming environments. In doing so we achieve state of the art approximation algorithms for weighted vertex cover, weighted maximum matching and weighted maximum independent set in the distributed setting. Many of our results in the distributed setting achieve optimal running time. In the semi-streaming model we present a deterministic (2 + ε)-approximation algorithm for maximum weight matching. This improves upon the previous best known approximation ratio of (3.5 + ε).

We also show how to apply property testing and derandomization techniques in the distributed settings. We initiate a thorough study of distributed property testing – producing algorithms for property testing problems in the CONGEST model. In particular, we present a distributed emulation technique for many sequential tests, and present distributed tests for triangle-freeness, cycle-freeness, and bipartiteness. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness. We also present tools for derandomizing solutions to local problems in the Congested Clique and CONGEST model. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model running in O(D log^2 n) rounds, where D is the diameter of the graph.

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 or PS files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2017
To the main CS technical reports page

Computer science department, Technion