EE Seminar: Distributed Interactive Proofs for Decision Tasks הנדסת חשמל
Zoom link: https://us02web.zoom.us/j/81297775131?pwd=b0dNZGpNaEJDbW5SQ1NyWjVSaWFiZz09
Meeting ID: 812 9777 5131
Passcode: TAUEESYS
Speaker: Dr. Ami Paz
CS, University Of Vienna
Tuesday, December 8th, 2020, at 15:00
Distributed Interactive Proofs for Decision Tasks
Abstract
One of the key concepts in complexity theory is decision tasks, where the goal is to decide if some predicate holds on the input. In *distributed* decision tasks, we are given a network of processing units, and wish to have the network decide a predicate on its own structure. Some predicates of interest are being bipartite, having diameter at most k or at least k, or containing a triangle.
In this talk, we will discuss labeling mechanisms that allow a network to decide such predicates fast, and with low communication. On the theoretical side, these can be seen as distributed nondeterministic decision mechanisms, and on the more practical side, as mechanisms for self stabilization. We will survey some techniques for exact and approximate decision, and discuss a recent concept of distributed interactive proofs.
Based on joint works with Keren Censor-Hillel, Pierluigi Crescenzi, Laurent Feuilloley, Pierre Fraigniaud, François Le Gall, Harumichi Nishimura and Mor Perry.
Short Bio
Ami Paz is a researcher in distributed computing. He is currently a post-doc at the University of Vienna, and before that he was a post-doc at IRIF, Paris. He obtained his PhD from the Technion in 2017, titled Distributed Distance Computation and Related Topics.
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בצ'אט
