Title: Distributed Convex Thresholding

Abstract
Over the last two decades years, a large group of algorithms emerged which compute various predicates from distributed data with a focus on communication efficiency. These algorithms are often called "communication-efficient", "geometric-monitoring", or "local" algorithms and are jointly referred as distributed convex thresholding (DCT) algorithms. DCT algorithms have found their applications in domains in which bandwidth is a scarce resource, such as wireless sensor networks and peer-to-peer systems, or in scenarios in which data rapidly streams to the different processors but outcome of the predicate rarely changes. Common to all of DCT algorithms is their use of a data dependent criteria to determine when further messaging is no longer required.

This work presents two very simple yet exceedingly general theorems which provide an alternative proof of correctness for any DCT algorithm. This alternative proof does not depend on the communication infrastructure and hence algorithms which depended on specific architectures (all but one of the previous work) are immediately extended to general networks. Because the theorems are general, they vastly extend the range of predicates which can be computed using DCT. Critical inspection of previous work in light of the new proof reveals that they contain redundant requirements, which cause unneeded messaging.

Work originally presented in PODC'15

Bio
Ran graduated from the computer science department of the Technion - Israel Institute of Technology. He previously held positions with the University of Maryland at Baltimore County and the department of information systems at the university of Haifa. In recent years he is a principle research scientist at Yahoo research, now a part of Verizon and still teaches privacy and information ethics courses at several Israeli universities. Ran's active research areas are data mining and the theory of privacy.

Meetings
His current academic focus is the theory of privacy and information ethics in general. Ran Wolff would like to invite interested students and faculty to discuss possible collaboration. For a preview of his work in this area please see https://www.pdcnet.org/jphil/content/jphil_2015_0112_0003_0141_0158. Please contact Jens Buß (jens.buss@tu-dortmund) for a time slot to talk to Ran Wolff.