Speaker: Dr. Moti Medina, Bar Ilan University

Date: 22/03/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: In this paper, we study the problem of testing graph isomorphism (GI) in the CONGEST distributed model. In this setting, we test whether the distributive network, G_U, is isomorphic to G_K which is given as an input to all the nodes in the network, or alternatively, only to a single node. We first consider the decision variant of the problem in which the algorithm should distinguish the case where G_U and G_K are isomorphic from the case where G_U and G_K are not isomorphic. Specifically, if G_U and G_K are not isomorphic then w.h.p. at least one node should output reject, and otherwise, all nodes should output accept. We provide a randomized algorithm with O(n) rounds for the setting in which G_K is given only to a single node. We prove that for this setting the number of rounds of any deterministic algorithm is Ω̃(n²) rounds, where n denotes the number of nodes, which implies a separation between the randomized and the deterministic complexities of deciding GI. Our algorithm can be adapted to the semi-streaming model, where a single pass is performed and Õ(n) bits of space are used. We then consider the property testing variant of the problem, where the algorithm is only required to distinguish the case that G_U and G_K are isomorphic from the case that G_U and G_K are far from being isomorphic (according to some predetermined distance measure). We show that every (possibly randomized) algorithm, requires Ω(D) rounds, where D denotes the diameter of the network. This lower bound holds even if all the nodes are given G_K as an input, and even if the message size is unbounded. We provide a randomized algorithm with an almost matching round complexity of O(D+(ε^{-1}log n)²) rounds that is suitable for dense graphs (namely, graphs with Ω(n²) edges). We also show that with the same number of rounds it is possible that each node outputs its mapping according to a bijection which is an approximate isomorphism. We conclude with simple simulation arguments that allow us to adapt centralized property testing algorithms and obtain essentially tight algorithms with round complexity Õ(D) for special families of sparse graphs.

This is a joint work with Reut Levi.

Bio: Moti has joined the Engineering Faculty at Bar-Ilan University in March 2021. Previously, he was a faculty member at the School of Electrical & Computer Engineering at Ben-Gurion University of the Negev, and before that, he was a post-doc researcher in D1: Algorithms and Complexity at Max-Planck-Institut für Informatik and, a post-doc researcher in the Algorithms and Complexity group at LIAFA (Paris 7).

He completed his Ph.D. studies at the School of Electrical Engineering at Tel-Aviv University, in 2014, under the supervision of Prof. Guy Even and Prof. Boaz Patt-Shamir. He has been awarded the national Eshkol 3-year Fellowship for his Ph.D. studies. The title of his Ph.D. dissertation is “Online Algorithms in Communication Networks”. He received his MSc degree from the school of Electrical Engineering at Tel Aviv University, in 2009, under the supervision of Professor Guy Even. He received his BSc in “Computer Science and Electrical Engineering” in 2007 at the school of Electrical Engineering at Tel Aviv University.

Moti is also a co-author of a text-book on logic design “Digital Logic Design: A Rigorous Approach”, Cambridge Univ. Press, Oct. 2012.

Speaker: Dr. Tigran Tonoyan, Technion

Date: 05/04/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: The talk will be about the following network design problem: Given a communication network of wireless nodes, find a spanning tree T of the network and a (time) schedule of the edges of T such that edges scheduled in every time slot are conflict-free, and the number of time slots is minimized. The problem is considered under a model of wireless interference that describes conflicts with fractional graphs. We will consider two simple approximation algorithms for this problem and its Steiner extension. The approximations are obtained in terms of a parameter called inductive independence of the conflict graph.

Bio: Tigran Tonoyan is a postdoc in Prof. Keren Censor-Hillel's group at the Technion, working on distributed graph algorithms. Before that, he was a postdoc at Reykjavik University in Iceland working with Prof. Magnus M. Halldorsson on approximation algorithms. He obtained a PhD degree in Computer Science from Geneva University in Switzerland, under the supervision of Prof. Jose D.P. Rolim. His research interests are in combinatorial optimization, approximation algorithms, and distributed graph algorithms, with an emphasis on problems inspired by communication networks.

Speaker: Yuval Dagan, Massachusetts Institute of Technology

Date: 19/04/2021

Time: 17:00-18:00

Zoom ID: 810 3573 2468

Abstract: Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning.

The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone's dimension, thus resolving the main open question from Ben-David, Pál, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).

Bio: Yuval Dagan is a PhD student at the EECS department of MIT. He received his Bachelor's and Master's degrees from the Technion.

Speaker: Dr. Manuj Mukherjee, Bar Ilan University

Date: 03/05/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: How many neurons are needed to approximate a target probability distribution using a neural network with a given input distribution and approximation error? This talk examines this question for the case when the input distribution is uniform, and the target distribution belongs to the class of histogram distributions. A new upper bound on the number of required neurons is obtained, which is strictly better than previously existing upper bounds. The key ingredient in this improvement is an efficient construction of the neural nets representing piecewise linear functions.

This is joint work with Aslan Tchamkerten and Mansoor Yousefi of Telecom Paris.

Bio: Manuj Mukherjee is a postdoctoral researcher at Bar Ilan University since 2020, working with Prof. Ran Gelles. Manuj completed his PhD from the Electrical Communication Engineering department of the Indian Institute of Science in 2017, under the supervision of Prof. Navin Kashyap. Prior to joining Bar Ilan University, he was a postdoctoral research at Telecom Paris (erstwhile Telecom ParisTech), working with Prof. Aslan Tchamkerten and Prof. Mansoor Yousefi.

Speaker: Prof. Amir Yehudayoff, Technion

Date: 24/05/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: How many hyperplanes are needed to slice all edges of the hypercube? This question has been studied in machine learning, geometry and computational complexity since the 1970s. We shall describe (parts of) an argument showing that more than Ω(n^{0.57}) hyperplanes are needed. We shall also see a couple of applications. This is joint work with Gal Yehuda.

Bio: Amir received his Ph.D. from the Weizmann Institute of Science and was a two-year member at the Institute for Advanced Study in Princeton. He is currently a professor in the Department of Mathematics at the Technion-Israel Institute of Technology. His main research area is theoretical computer science, with a recent focus on learning theory and information theory.

Speaker: Rishabh Bhadauria, Bar Ilan University

Date: 07/06/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: This work follows the line of works that design concretely efficient transparent sublinear zero-knowledge Interactive Oracle Proofs (IOP). Arguments obtained via this paradigm have the advantages of not relying on public-key cryptography, not requiring a trusted setup, and resistance to known quantum attacks. In the realm of transparent systems, Ligero and Aurora stand out with incomparable advantages where the former has a fast prover algorithm somewhat succinct proofs and the latter has somewhat fast prover and succinct proofs. In this work, we introduce Ligero++ that combines the best features of both approaches to achieve the best of both worlds.

This is a joint work with Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramanium, Tiancheng Xie and Yupeng Zhan.

Bio: Rishabh Bhadauria is a PhD student in Engineering Faculty at Bar-Ilan University, under the supervision of Prof. Carmit Hazay. He received his Bachelor's and Master's degree from IIIT-Bangalore.

Speaker: Prof. Yuval Emek, Technion

Date: 21/06/2021

Time: 13:00-14:00

Zoom ID: 810 3573 2468

Abstract: Introduced by Emek and Wattenhofer (PODC 2013), the stone age (SA) model provides an abstraction for network algorithms distributed over randomized finite state machines. This model, designed to resemble the dynamics of biological processes in cellular networks, assumes a weak communication scheme that is built upon the nodes' ability to sense their vicinity in an asynchronous manner. Recent works demonstrate that the weak computation and communication capabilities of the SA model suffice for efficient solutions to some core tasks in distributed computing, but they do so under the (somewhat less realistic) assumption of fault free computations. In this talk, we initiate the study of self-stabilizing SA algorithms that are guaranteed to recover from any combination of transient faults. Specifically, we develop efficient self-stabilizing SA algorithms for the leader election and maximal independent set tasks in bounded diameter graphs subject to an asynchronous scheduler. These algorithms rely on a novel efficient self-stabilizing asynchronous unison (AU) algorithm that is ``thin'' in terms of its state space: the number of states used by the AU algorithm is linear in the graph's diameter bound, irrespective of the number of nodes.

Based on a joint work with Eyal Keren. The talk will be self-contained.

Bio: Yuval Emek graduated summa cum laude from Technion – Israel Institute of Technology with a bachelor degree in computer science (2000) and completed his master studies (2003) and Ph.D. (2008) in computer science and applied mathematics at Weizmann Institute of Science under the advise of David Peleg. Following that, he held post-doc positions at Tel Aviv University (2008-2009, Boaz Patt-Shamir’s group), Microsoft (2009-2010, Moshe Tennenholtz’s group), and ETH Zurich (2010-2013, Roger Wattenhofer’s group). In 2013, Yuval joined the Faculty of Industrial Engineering and Management in the Technion.