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
Mina Konakovic Lukovic (MIT Computer Science and Artificial Intelligence Lab)
Zoom Lecture: https://technion.zoom.us/j/91344952941
Recent advances in material science and digital fabrication provide promising opportunities for product design, mechanical and biomedical engineering, robotics, architecture, art, and science. Engineered materials and personalized fabrication are revolutionizing manufacturing culture and having a significant impact on various scientific and industrial works. As new fabrication technologies emerge, effective computational tools are needed to fully exploit the potential of digital fabrication. In this talk, I will discuss how we use the insights from discrete differential geometry to enable designs not possible before and design new materials with specific properties and performance. We introduce a novel computational method for design and fabrication with auxetic materials. The term auxetic refers to solid materials with a negative Poisson ratio — when the material is stretched in one direction, it also expands in all other directions. In particular, we study 2D auxetic materials in the form of a triangular linkage that exhibits auxetic behavior at the macro scale. This stretching, in turn, allows the flat material to approximate doubly-curved surfaces, making it attractive for fabrication. Furthermore, we develop a computational method for designing novel deployable structures via programmable auxetics, i.e., spatially varying triangular linkage optimized to directly and uniquely encode the target 3D surface in the 2D pattern. In contrast to most previous work, our approach is scale-invariant. It can be applied to realize a broad class of complex curved surfaces, ranging from tiny medical implants to large scale architectural domes.
Yaron Fairstein (CS, Technion)
Wednesday, 9.12.2020, 12:30
Zoom, Meeting ID: 954 7347 4134, Password: 5-digit Technion Zip Code
We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP). The input is a set I of items, each associated with a non-negative weight, and a set of bins, each having a capacity. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a subset of items A⊆I and a packing of the items in the bins, such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint.
Our main result is a nearly optimal polynomial time (1−e–1–ε)-approximation algorithm for the problem, for any ε>0. Our algorithm relies on a refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems.
Joint work with Ariel Kulik, Seffi Naor, Danny Raz, and Hadas Shachnai.
Yamit Barshatz, M.Sc. Thesis Seminar
Wednesday, 16.12.2020, 13:00
Zoom Lecture: https://technion.zoom.us/j/95176272923
Advisor: Prof. R. Friedman
Programmable switches are advanced network switches that can be programmed to perform certain actions besides routing packets. Programmable switches enable combining the logic and flexibility of software with the speed and efficiency of hardware and thus enjoy the benefits of both. Interstingly, programmable switches are also 2-3 orders of magnitude more power to compute efficient than GPUs and FPGAs. Alas, they offer a very restricted and non-intuitive programming model.
Sorting is a fundamental and well studied problem that has been studied extensively. Sorting plays a very important role in the area of databases, as many queries can be served much faster if the relations are first sorted. Merge sort is a very popular sorting algorithm in databases.
In modern data-centers, data is stored in storage servers, while processing takes place in compute servers. Hence, in order to compute queries on the data, the data must travel through the network from the storage servers to the computing servers. This creates a potential for using programmable switches to perform partial sorting in order to accelerate the sorting process at the server side. This is possible because, as mentioned above, the data packets pass through the switch in any case on their way to the server.
We devised a partial sorting algorithm that fits the programming model and restrictions of programmable switches. Our approach changes the order in which data is emitted from the switch. We also utilize built-in parallelism in the switch to divided the data into sequential ranges. Thus, the server needs to sort each range separately and then concatenate them to one sorted stream. The end result is that the server needs to sort smaller sections and each of these sections is already partially sorted. Hence, the server does less work, and the access pattern becomes more virtual memory and hardware cache friendly.
We examine several data stream compositions with various switch configurations. Our study exhibited an improvement of 30\%-60\% in the sorting run-time when using our approach compared to plain sorting on the original stream. This suggests that our algorithm can significantly reduce the execution time at the servers.
Gal Sade, M.Sc. Thesis Seminar
Sunday, 20.12.2020, 16:00
Zoom Lecture: https://technion.zoom.us/j/94459929157
Advisor: Prof. O. Grumberg
Model checking is an automatic verification method that accepts a system model and a specification, and checks whether the model satisfies the specification. CTL is a branching temporal logic suitable for specifying behaviors of both software and hardware systems.
In this work, we present a novel approach that combines on-the-fly verification with abstraction in order to obtain an efficient model checking.
On-the-fly verification ensures that only parts that are needed for determining the satisfaction of the specification are developed. The abstraction is used to generalize information that was computed on fragments of the model, thus allowing the algorithm to halt without developing the entire model.
We implemented our algorithm, compared it with a state-of-the-art CTL model checker and received very encouraging results.