# 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.

- CGGC Weekly Seminar
- Coding Theory Seminar
- Colloquia
- Hardware Security Seminar
- Pixel Club
- Theory of Data Science and Deep Learning
- Theory Seminar

## Upcoming Colloquia & Seminars

### Overlapping Correlation Clustering in Theory

- Speaker:
- Ayelet Kravi, M.Sc. Thesis Seminar
- Date:
- Thursday, 14.11.2019, 11:00
- Place:
- Room 601 Taub Bld.
- Advisor:
- Prof. Roy Schwarz and Prof. Seffi Naor

The overlapping correlation clustering problem has multiple real-world applications in diverse areas such as: social networks (community detection), biology (protein analysis) and information retrieval (categorising documents). Correlation clustering is a problem of assigning data points into distinct groups (clusters) based on similarity. When assigning two similar data points to the same cluster or assigning two different data points to different clusters, we score this assignment as successful, otherwise, we score the assignment as unsuccessful. When solving the correlation clustering problem, two optional objectives are to minimise the disagreement (the number of unsuccessful assignments) or to maximise the agreement (the number of successful assignments). In overlapping correlation clustering, we are allowing the clusters to intersect, meaning a single data point may belong to multiple clusters. In the overlapping version, we use the Jaccard similarity coefficient (a function that quantify the similarity between two given sets) to measure how successful is our assignment. We studied the overlapping correlation clustering problem from theoretical perspective by formulating a liner relaxation and trying to solve it. We focused on a sub-problem of finding overlapping multiway-cut. Using linear relaxation, we managed to achieved an O(1+alpha)-approximation algorithm.

### Machine Learning of SQL Queries Containment Rate and Result Cardinality

- Speaker:
- Rojeh Hayek, M.Sc. Thesis Seminar
- Date:
- Sunday, 17.11.2019, 15:30
- Place:
- Room 601 Taub Bld.
- Advisor:
- Prof. Oded Shmueli

Traditional query optimizer is crucially dependent on cardinality estimation, which enables choosing among different plan alternatives by using the cardinality estimation of intermediate results within query execution plans. Therefore, the query optimizer must use reasonably good estimates. However, estimates produced by all widely-used database cardinality estimation models are routinely significantly wrong, resulting in not choosing the best plans, leading to slow executions. In this work we define a new problem, that of estimating the containment rate between pairs of SQL queries, and we introduce a novel technique for estimating queries’ result-cardinalities using estimated queries’ containment rates. For estimating containment rates between SQL queries, we propose a specialized deep learning model, CRN, which enables us to express query features using sets and vectors. We show that using the proposed technique for estimating cardinalities with the CRN model, we improve current cardinality estimation techniques significantly. This is especially the case when there are multiple joins, where the known cardinality estimation techniques suffer from under-estimated results and errors that grow exponentially as the number of joins increases. Our technique estimates the cardinalities more robustly x150/x175 with 4 joins queries, and x1650/x120 with 5 joins queries, compared with the PostgreSQL cardinality estimation component, and MSCN, a state-of-the-art cardinality estimation model, respectively. We also show that by employing any existing cardinality estimation method such as PostgreSQL, for containment estimation, and then embedding it in our cardinality estimation technique, we improve on its cardinality estimates as well, without changing the method itself. Additionally, we propose two techniques for extending any “limited” cardinality estimation model that only estimates cardinalities with duplicates of conjunctive queries, to support general queries that use the AND, OR, and NOT operators, and to be able to estimate the set-theoretic cardinalities (i.e., cardinalities without duplicates). -The talk will be given in Hebrew.

### Data Science & Deep Learning Seminar: Discrepancy, Coresets, and Sketches in Machine Learning

- Speaker:
- Edo Liberty
- Date:
- Monday, 18.11.2019, 12:30
- Place:
- Taub 301 Taub Bld.

This paper defines the notion of class discrepancy for families of functions. It shows that low discrepancy classes admit small offline and streaming coresets. We provide general techniques for bounding the class discrepancy of machine learning problems. As corollaries of the general technique we bound the discrepancy (and therefore coreset complexity) of logistic regression, sigmoid activation loss, matrix covariance, kernel density and any analytic function of the dot product or the squared distance. Our results prove the existence of epsilon-approximation O(sqrt{d}/epsilon) sized coresets for the above problems. This resolves the long-standing open problem regarding the coreset complexity of Gaussian kernel density estimation. We provide two more related but independent results. First, an exponential improvement of the widely used merge-and-reduce trick which gives improved streaming sketches for any low discrepancy problem. Second, an extremely simple deterministic algorithm for finding low discrepancy sequences (and therefore coresets) for any positive semi-definite kernel. This paper establishes some explicit connections between class discrepancy, coreset complexity, learnability, and streaming algorithms.

Edo is the founder of a stealth-mode company in the machine learning and cloud computing space. Until April 2019 he was a Director of Research at AWS and the manager Amazon AI Labs. The Lab built cutting edge machine learning algorithms, systems, and services for AWS customers. They build parts of SageMaker, Kinesis, QuickSight, Amazon Elastic Search, Glue, Rekognition, DeepRacer, Personalize, Forecast, and other yet-to-be-released services from AWS.### Pixel Club: What's in a Face? Metric Learning for Face Characterization

- Speaker:
- Omry Sendik, Dani Lischinski and Daniel Cohen-Or (Tel-Aviv University)
- Date:
- Tuesday, 19.11.2019, 11:30
- Place:
- Electrical Eng. Building 1061

We present a method for determining which facial parts (mouth, nose, etc.) best characterize an individual, given a set of that individual's portraits. We introduce a novel distinctiveness analysis of a set of portraits, which leverages the deep features extracted by a pre‐trained face recognition CNN and a hair segmentation FCN, in the context of a weakly supervised metric learning scheme. Our analysis enables the generation of a polarized class activation map (PCAM) for an individual's portrait via a transformation that localizes and amplifies the discriminative regions of the deep feature maps extracted by the aforementioned networks. A user study that we conducted shows that there is a surprisingly good agreement between the face parts that users indicate as characteristic and the face parts automatically selected by our method. We demonstrate a few applications of our method, including determining the most and the least representative portraits among a set of portraits of an individual, and the creation of facial hybrids: portraits that combine the characteristic recognizable facial features of two individuals. Our face characterization analysis is also effective for ranking portraits in order to find an individual's look‐alikes (Doppelgängers).

### ceClub: Beresheet's Journey to The Moon

- Speaker:
- Noam Leiter (AE. Technion)
- Date:
- Wednesday, 20.11.2019, 11:30
- Place:
- Electrical Eng. Building 861

SpaceIL made history when Beresheet, the first privately funded spacecraft, have reached the Moon with a minute budget of 100M$. After eight years of planning, Beresheet's journey started on February 22nd, 2019, when SpaceIL's lunar lander has been launched to space on top of a Falcon 9 launcher. During its 49 days space journey, Beresheet performed a series of successful autonomous maneuvers that brought it from Earth orbit to lunar orbit, and on April 11th, 2019 after orbiting the Moon for seven days the landing sequence was initiated. A few minutes into the landing a series of events ended in the main thruster shutdown and Beresheet crashed into the Moon, adding Israel to the exclusive club of countries that reached the moon and inspiring millions from across the globe to dream big. This talk will unravel some of the algorithmic and software technological challenges of this fascinating journey and the important lessons learned.

Bio:

Noam Leiter has received his B.Sc. in 2011 and M.Sc. in 2015, both in aerospace engineering at the Technion. He has been working as a control engineer for SpaceIL from 2014 until 2019, developing spacecraft guidance and control algorithms. He is currently pursuing a Ph.D. in the faculty of aerospace engineering at the Technion under the supervision of Prof. Dan Zelazo.### Theory Seminar: Scheduling Algorithms in the SINR Model for Wireless Networks

- Speaker:
- Tigran Tonoyan (CS. Technion)
- Date:
- Wednesday, 20.11.2019, 12:30
- Place:
- Taub 201 Taub Bld.

SINR (aka physical model) is a model of wireless communication that has been studied from algorithmic perspective in the last decade, and is considered as a more realistic alternative to the traditional graph-based models. I will introduce the model and discuss some basic scheduling problems. At a high level, these can be thought of as coloring or independent set problems in some special fractional graphs.

### Degree-Bounded Polymatroids, with Applications to the Many-Visits TSP

- Speaker:
- Matthias Mnich - COLLOQUIUM LECTURE
- Date:
- Tuesday, 3.12.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- University of Bonn
- Host:
- Hadas Shachnai

In the Bounded Degree Matroid Basis Problem, we are given a matroid and a hypergraph on the same ground set, together with costs for the elements of that set as well as lower and upper bounds f(e) and g(e) for each hyperedge e. The objective is to find a minimum-cost basis B such that f(e) <= |B \cap e| <= g(e) for each hyperedge e. Kiraly, Lau and Singh (Combinatorica, 2012) provided an algorithm that finds a basis of cost at most the optimum value which violates the lower and upper bounds by at most 2\Delta-1, where \Delta is the maximum degree of the hypergraph. We consider an extension of the matroid basis problem to generalized polymatroids, and additionally allow element multiplicities. Building on the approach of Kiraly, Lau and Singh, we provide an algorithm for finding a solution of cost at most the optimum value having the same additive approximation guarantee. As an application, we develop a 1.5-approximation for the metric many-visits TSP, where the goal is to find a minimum-cost tour that visits each city v a positive number r_v of times. Our approach combines our algorithm for the Lower Bounded Degree Generalized Polymatroid Basis Problem with Multiplicities with the principle of Christofides' algorithm from 1976 for the (single-visit) metric TSP, whose approximation guarantee it matches. We also present a new algorithm for the general many-visits TSP without any metric assumptions on the edge cost. For this problem, Cosmadakis and Papadimitriou (SICOMP, 1984) provided an algorithm that finds an optimal tour in time and space that depends superexponentially on the number of cities. We give an improved algorithm which simultaneously improves the time complexity to single-exponential, and the space complexity to polynomial. Assuming the Exponential Time Hypothesis, the run time of our algorithm is asymptotically optimal. Our algorithm is arguably simpler than the one by Cosmadakis and Papadimitriou. (Based on joint work with Kristof Berczi, Andre Berger, Tamas Kiraly, Laszlo Kozma, Gyula Pap and Roland Vincze) Short Bio: ========== Matthias Mnich is an assistant professor of quantitative economics at Maastricht University, The Netherlands, currently on leave for research in theoretical computer science at the Rheinische Friedrich-Wilhelms Universitaet Bonn, Germany. He obtained his PhD in 2010 at Eindhoven University of Technology, for which he received the Philips Prize 2010. Since then he held positions at UC Berkeley, USA and the Max Planck Institute for Computer Science, and a visiting professorship at TU Darmstadt, Germany. His research interests are in combinatorial algorithms, social choice theory, algorithms for big data, and algorithms in artificial intelligence. ================================================== Refreshments will be served from 14:15 Lecture starts at 14:30

### MPC Beyond the Generic Model - Private Intersection Analytics

- Speaker:
- Benny Pinkas - COLLOQUIUM LECTURE
- Date:
- Tuesday, 10.12.2019, 14:30
- Place:
- Room 337 Taub Bld.
- Affiliation:
- Dept. of Computer Science, and Center for Research in Applied Cryptography and Cyber Security, Bar-Ilan University
- Host:
- Yuval Filmus

Effective data analysis often depends on data that is known to different sources, including private data whose owners cannot disclose. The task at hand is to perform effective analysis of the data while preserving its privacy. This talk will describe efficient cryptographic protocols, some of them based on variants of private set intersection (PSI), that can be applied to perform private analysis of data. Short Bio: ============ Benny Pinkas is a member of the Bar Ilan Cryptography Group and the Center for Research in Applied Cryptography and Cyber Security. His reserach focuses on computer security, privacy and cryptography, and in particular on the design of efficient security systems based on sound assumptions and solid proofs. During the 2011/2 academic year he was also on sabbatical at Google Research. He previously worked at the University of Haifa, at HP Labs in Haifa and in Princeton, and at STAR Lab, Intertrust Technologies. Before that he was a Ph.D. student of Moni Naor at the Foundations of Computer Science Group at the Department of Computer Science and Applied Math in the Weizmann Institute of Science. ========================================= Rereshments will be served from 14:15 Lecture starts at 14:30