​​Seminar1.jpg

​​For updates about future department seminars, you are welcome to join our mailing list.​​


Title

​When

​​​​Abstract​

Algorithms for Approximation of Random Variables

By Liat Cohen
(Adviser Prof. Gera Weiss)

Dec. 1, 2020
13:00-14:00

>> Zoom Link
​In planning algorithms, scheduling, and other domains, there is often a need to run long computations on random variables, and to store intermediate results. A source of computational complexity often neglected in the analysis of such algorithms, is that the support, the number of non-zero probability values, of the variables needed as intermediate results may grow exponentially along the computation. To avoid exponential memory and time complexities, we suggest to shrink the support of those variables in ways that yield good approximations. In this work we introduce algorithms and methods for approximating random variables under the Kolmogorov metric in which the support size can be maintained, however, with a cost of an error.
As a motivating example that demonstrates the importance of the problem and also accentuates the NP-hardness of the problem we study the use-case of estimating the probability that a plan makespan meets a given deadline; we call this problem the Deadline Problem. We present the results, provide an elaborated theoretical analysis for the approximation algorithms and also an empirical evaluation. Finally, we conclude and present the main contributions of this work, the significance of the papers and a suggested future work.

>> Meeting Recording

Static ​​and Streaming Data Structures for Fréchet Distance Queries​

By Dr. Omrit Filtser
Nov. 24, 2020
16:30-17:30


Measuring the similarity of two curves or trajectories is an important task that arises in various applications. The Fréchet distance and its variants became very popular in the last few decades, and some variants were successfully applied to real data sets. The Fréchet distance between two curves can be computed in quadratic time using a simple dynamic programming algorithm. However, under SETH, no strongly subquadratic algorithms exist, even if the solution may be approximated up to a factor of 3. In applications where there is a need to compute the distance to a single curve many times, or when the input curve is extremely large and quadratic running time is infeasible, a natural solution is to construct a data structure that allows fast distance queries. In this talk Dr. Filtser will discuss approximate distance oracles and nearest neighbour search data structures under the discrete Fréchet distance. In addition, she will present an algorithm that constructs simplifications in the streaming model, an oracle for distance queries to a sub-curve, and introduce the zoom-in problem.

The talk is based on the following papers:
* Static and Streaming Data Structures for Fréchet Distance Queries (SODA'21) - joint work with Arnold Filtser.
* Approximate Nearest Neighbor for Curves - Simple, Efficient, andDeterministic (ICALP'20) - joint work with Arnold Filtser and Matya Katz.

A Differential Geometry​ Persp​ective on Sequential Models

By Dr. Omri Azencot
Nov. 17, 2020
12:00-13:00

We introduce a new framework for the analysis and processing of time-series data and sequential models. Based on Koopman theory and its application to mappings, we propose a new interpretation for a recent family of state-of-the-art orthogonal recurrent models. Then, we observe that orthogonal models have limited expressivity, and we suggest a new recurrent architecture that alleviates this shortcoming. Then, we show how to easily control the behavior of our model using simple regularization components. We evaluate our approach on several benchmarks, and we discuss its advantages over prior models.​​​
Concise Essence-Preserving Big Data Representations

By Philip Derbeko
(Advisers: Prof. Shlomi Dolev, Prof. Ehud Gudes)


​Nov. 10, 2020
12:00-13:00

 
 
​The amount of data grows rapidly with time and shows no signs of stopping. Computers have become smaller and more abundant. Devices get more sensors and wireless connectivity. All of them collect more data about their surroundings and, usually, send it to the cloud servers for processing. In the end, more data is collected and processed to get more insights into how to serve us better. The common premise is that more data leads to better insights. However, as the processing, storage and transfer of the data require an increasing amount of resources, the question is: is more data always worth its cost?
In this research, we consider a different approach to dealing with increasing amounts of data. Instead of preparing for more data, we try to reduce the amount of collected, transmitted, stored, and processed data. In doing so, we hope to reduce the resource consumption of all participants from end-devices through the network and to the cloud providers, and support prompt answers to (the statistical in nature) queries. To reduce the amount of data we suggest using a smaller, representative data model. We call it the similitude model. The model represents the original dataset, i.e. it can be used to answer data queries while being much smaller than the data in size.
​Research-oriented zoom meetings for new MSc. students - Round 2

​Nov. 03, 2020
12:00-13:00

>> ​Zoo​m Link
 
​This is the second of two small research-oriented zoom meetings of students and faculty members, intended mostly for new students who did not find an adviser yet (other students and faculty are obviously welcome).
There will be 4-5 faculty mem​bers presenting their research at each meeting. These faculty members, and others that will also attend the meetings, are looking for new research students, and this is a good opportunity to get acquainted and talk to them. If you haven't done so already, we encourage you to visit our department's research page and follow the links according to your field(s) of interest.

>> Meeting Recording

Research-oriented zoom meetings for new MSc. students - Round 1
Oct. 27, 2020
12:00-13:00

>> ​Zoo​m Link
This is the first of two small research-oriented zoom meetings of students and faculty members, intended mostly for new students who did not find an adviser yet (other students and faculty are obviously welcome).
There will be 4-5 faculty mem​bers presenting their research at each meeting. These faculty members, and others that will also attend the meetings, are looking for new research students, and this is a good opportunity to get acquainted and talk to them. If you haven't done so already, we encourage you to visit our department's research page and follow the links according to your field(s) of interest.

>> Meeting Recording