The talks for this edition will be held every other week starting October 18th, 2021. The talks take place in classroom 2 in the dormitories building (A1300), and are scheduled on Mondays from 14:00-16:00 (local time), with gathering and refreshments at 14:00, and talks starting at 14:30. A detailed program is given below.
Speaker: Dr. Manuj Mukherjee, Bar-Ilan University
Date: 18/10/2021
Time: 14:00-16:00
Abstract: We consider computations over networks with multiple broadcast channels that intersect at a single party. Each broadcast link suffers from random bit-flip noise that affects the receivers independently. We design interactive coding schemes that successfully perform any computation over these noisy networks and strive to reduce their communication overhead with respect to the original (noiseless) computation.
A simple variant of a coding scheme by Rajagopalan and Schulman (STOC 1994) shows that any (noiseless) protocol of rounds can be reliably simulated in rounds over a network with parties in which a single party is connected to noisy broadcast channels, each of which connects distinct parties. We design new coding schemes with improved overheads. Our approach divides the network into four regimes according to the relationship between and . We employ a two-layer coding where the inner code protects each broadcast channel and is tailored to the specific conditions of the regime in consideration. The outer layer protects the computation in the network and is generally based on the scheme of Rajagopalan and Schulman, adapted to the case of broadcast channels. The overhead we obtain ranges from to and beats the trivial overhead in all four regimes.
Based on a joint work with Ran Gelles.
Speaker: Dr. Or Sheffet, Bar-Ilan University
Date: 1/11/2021
Time: 14:00-16:00
Abstract: In the last couple of decades, several combinatorial bounds and algorithmic results were obtained using techniques that are derived from Information Theory. In this talk we will survey a few of them, demonstrating just how widely applicable such techniques are. A tentative list: bounding the number of cliques in a graph, proving Bregman's theorem, and the classic LLL algorithm. Time permitting we may attempt to cover also the notion of graph entropy and Kahn and Kim's sorting algorithm.
The talk is self-contained and no prior knowledge is assumed.
References:
* An entropy proof of Bregman's theorem, Radhakrishnan J., Journal of Combinatorial Theory, Series A, Vol.77, number 1, January 1977.
* A constructive proof of the Lovász local lemma, STOC 2009 Proceedings of the 41st annual ACM symposium on Theory of computing.
* Anup Rao's "Information theory in computer science" course notes: https://catalyst.uw.edu/workspace/anuprao/15415/86751
* Graph entropy: a survey, Simonyi G., Combinatorial Optimization, DIAMCS Series in Discrete Mathematics and Theoretical Computer Science, Vol.20, AMS, 1995.
* Entropy and sorting, Kahn J. and Kim J.H., STOC '92 Proceedings of the twenty-fourth annual ACM symposium on Theory of computing
Speaker: Gilad Dar, Bar-Ilan University
Date: 15/11/2021
Time: 14:00-16:00
Abstract: Fine-grained Control Flow Checkers (CFCs) identify fault injection attacks on storing elements containing the executable program with instruction level granularity. MAC-based CFCs utilized signatures to detect such violations without modifying the program’s instructions. Nevertheless, most current solutions cause high performance overheads, set limitations on the size of the verified blocks, or require an expensive tamper-proof memory to store the signatures. Our work presents a scalable light-weight fine-grained CFC which can detect any error in the program itself even if the signature was tampered with. We show concurrent implementation for 32/64-bit architecture and prove its error detection capabilities both analytically and in practice. Then, we generalize the proposed CFC to support other architectures as well.
Speaker: Dr. Nir Halman, Bar-Ilan University
Date: 27/12/2021
Time: 14:00-16:00
Abstract: In this paper we go one step further in the automatic generation of FPTASes for multi-stage stochastic dynamic programs with scalar state and action spaces, where the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is general and simple enough to be extensively used. We believe that our framework has these two attributes, and has great potential to attract interest from both the operations research and theoretical computer science communities.
Joint work with Tzvi Alon, to appear in SIDMA.
Speaker: Tamuz Danzig, Bar-Ilan University
Date: 10/01/2022
Time: 14:00-16:00
Abstract: Quantum computing, which offers a new and entirely different computation scheme, has the potential to significantly outperform classical computing in certain hard computational tasks, such as integer factorization. However, existing quantum computers are small and noisy, thereby heavily limited in performance. A family of recent hybrid algorithms, which combines both classical and quantum computing, has become very popular due to its relative noise resistance and its applicability on existing noisy quantum hardware. In this talk, following a short overview on quantum computation, I will focus on a particular hybrid quantum-classical algorithm, called quantum approximate optimization algorithm (QAOA) and show how it can be used for solving combinatorial optimization problems. Then, in the last part of the talk, I will describe some of our ideas for how to extend the QAOA algorithm and show preliminary results.
Speaker: Anasuya Acharya, Bar-Ilan University
Date: 21/03/2022
Time: 14:00-16:00
Abstract: Secure Multiparty Computation (MPC) deals with multiple entities having private inputs communicating in a protocol to jointly compute a function of their inputs. This is done in such a way that no information, beyond the function output, is revealed. One standard tool used historically for secure computation is garbled circuits (GC). In the two party setting, a GC-based protocol typically involves one party (a garbler) encoding the circuit of the function to be computed into a garbling. This garbled circuit is given to the other party (the evaluator) along with a secret encoding of function inputs and it derives the function output. Moving from the 2-party setting to the multiparty setting with all-but-one corruption, it becomes necessary that all-but-one of the parties be involved in an MPC protocol to generate the GC.
This talk is based on joint work with Carmit Hazay, Vladimir Kolesnikov and Manoj Prabhakaran. We provide a means for performing multiparty garbling that requires communication linear in both the number of parties and the circuit size. In particular, we define Rerandomizable Garbled Circuits (RGC), a primitive which allows the process of multiparty garbling to be serialized: one party initially garbles the circuit and then every other party takes a garbled circuit and adds their private randomness to it. This primitive allows protocols to remain secure in the presence of all-but-one semi-honest corruption. RGCs also enjoy other interesting applications like outsourced regarbling: a party having a secret function can garble its circuit once and give the GC to a server that creates several rerandomized copies of it for it to be evaluated with different inputs.
Speaker: Dr. Itamar Levi, Bar-Ilan University
Date: 04/04/2022
Time: 14:00-16:00
Abstract: The integration of trillions of wireless sensing, computing and communicating nodes in the “Internet of Things” is a reality which considerably affects our lives. Whereas it brings breakthrough opportunities for a wide range of applications (e.g., automotive, smart grids/cities, medical implants and industrial cyber-physical systems), it serves as a concrete challenge for security, integrity and privacy. Perhaps the most challenging aspect relates to the physical-security of these devices due to their physical exposure and accessibility. Moreover, the cost of securing these devices, to-date, is simply too high for their specifications (i.e. low energy, small area, large range of activity-factor). This talk will start with a brief introduction to this field of research, discussing limitations of state-of-the-art “consensus” approaches to protect against physical attacks by adversaries which utilize side-channels (e.g., masking by secret-sharing). For example, it will be demonstrated how an adversary which is aware of the physical aspects of the devices (electronics, architecture etc.) can easily crumble the theoretical security promises of such constructions. Then, it will be shown how a close interaction between crypto. algorithms, architectures and platforms can foster considerable security- and performance-improvement of countermeasures and novelty. We will walk through software and hardware optimizations. Finally, we discuss an alarming class of remote threats, where near-field emanation is amplified and coupled to RF channels and conclude with a goal of open-sourcing hardware-security.
Speaker: Prof. Zvi Lotker, Bar-Ilan University
Date: 02/05/2022
Time: 14:00-16:00
Abstract: In this talk I will present two key ideas from my book "Analyzing Narratives in Social Networks" regarding time and space, and social networks.
In the first part of the talk we will discuss how to create room for interpretation, moving away from the paradigm in which the computer is an expert that only provides definitive answers and moving towards the paradigm in which we have a space for dialogue with the computer.
In the second part of the talk we will discuss the meaning of subjective time and how to work with it. We will see how to measure subjective time using clocks, comparing it to other clocks, and how to use them to help interpret narrative.
Speaker: Dr. Anatoly Khina, Tel-Aviv University
Date: 16/05/2022
Time: 14:00-16:00
Abstract: What is the maximal speed—the information velocity—at which information can propagate reliably in a network through a cascade of links?
Information theory tells us what is the maximal rate of reliable communications through a small number of such links when delay is not important. However, if we want to communicate in real time, answering this question becomes much more challenging. In fact, even for the simple case of transmitting a single bit over a tandem of links, where each flips its input independently (across time & links), an answer was given only very recently.
In this talk, I will present some recent results for this problem for packet-based links with ACK signals. In particular, I will derive the information velocity for a causally arriving stream of packets, and determine the arrive-failure exponential decay rate below the information velocity.
No prior knowledge of information theory or queueing theory will be assumed.
Joint work with Elad Domanovitz & Tal Philosof.
Mor Weiss - mor.weiss@biu.ac.il