Colloquia and Seminars
To join the email distribution list of the cs colloquia, please visit the list subscription page.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
Upcoming Colloquia & Seminars
Majd Khalil, M.Sc. Thesis Seminar
Monday, 25.10.2021, 13:30
Advisor: Prof. Benny Kimelfeld
A path query extracts from the input graph the pairs of vertices that constitute the endpoints of matching paths, that is, paths such that the word obtained from the edge labels belongs to a specified language. We study the computational complexity of measuring the contribution of edges and vertices to an answer of a path query.
For that, we adopt the traditional Shapley value from cooperative game theory. This value has recently been suggested and studied as a standard contribution measure for database queries, machine-learning classifiers, and so on.
We start by showing that the exact Shapley value is almost always hard to compute. For example, we show that (under conventional complexity assumptions) the Shapley value of an edge can be computed in polynomial time if and only if the path language has only words of length at most two.
On the other hand, it is straightforward to obtain an efficient scheme (FPRAS) for an additive approximation. Yet, a multiplicative approximation is harder to obtain. We establish that in the case of a regular language, a multiplicative approximation of the Shapley value of an edge can be computed in polynomial time if and only if the path language is finite.
Evgenii Zheltonozhskii , M.Sc. Thesis Seminar
Tuesday, 26.10.2021, 14:30
Advisor: Prof. A. Mendelson, Prof. A. Bronstein, Dr. C. Baskin
While deep neural networks (DNNs) have shown tremendous success across various computer vision tasks, including image classification, object detection, and semantic segmentation, requirements for a large number of high-quality labels obstruct the adoption of DNNs in real-life problems. Lately, researchers have proposed multiple approaches for reducing requirements to the amount or quality of these labels or even working in a fully unsupervised way. In a series of works, we study different approaches to supervision reduction in visual recognition tasks: self-supervised learning, learning with noisy labels, and semi-supervised learning. For self-supervised learning, we show that dimensionality reduction followed by simple k-nearest neighbors clustering is a very strong baseline for fully unsupervised large-scale classification (ImageNet). Additionally, we present a learning with noisy labels framework comprising two stages: self-supervised pre-training and robust fine-tuning. The framework, dubbed "Contrast to Divide" (C2D), significantly outperforms prior art on synthetic and real-life noise, showing state-of-the-art performance with different methods and pre-training approaches. Furthermore, since self-supervised pre-training is unaffected by label noise, C2D is especially efficient in a high noise regime. Finally, for semi-supervised learning, we propose a simple weighting scheme that reduces confirmation bias among unlabeled samples and, as a result, outperforms existing methods on different datasets and a wide range of labeled sample fractions. The talk will be given in English.
Koral Chapnik, M.Sc. Thesis Seminar
Tuesday, 2.11.2021, 17:00
Advisor: Prof. Assaf Schuster, Dr. Ilya Kolchinsky
CComplex event processing (CEP) is widely employed to detect user-defined combinations, or patterns, of events in massive streams of incoming data. Numerous applications such as healthcare, fraud detection, and more, use CEP technologies to capture critical alerts, threats, or vital notifications. This requires that the technology meet real-time detection constraints. Multiple optimization techniques have been developed to minimize the processing time for CEP, including parallelization techniques, pattern rewriting, and more. However, these techniques may not suffice or may not be applicable when an unpredictable peak in the input event stream exceeds the system capacity. In such cases, one immediate possible solution is to drop some of the load in a technique known as load shedding.
We present a novel load shedding mechanism for real-time complex event processing. Our approach uses statistics that are gathered to detect overload. The solution makes data-driven load shedding decisions to drop the less important events such that we preserve a given latency bound while minimizing the degradation in the quality of results. An extensive experimental evaluation on a broad set of real-life patterns and datasets demonstrates the superiority of our approach over the state-of-the-art techniques.