Colloquia and SeminarsTo join the email distribution list of the cs colloquia, please visit the list subscription page.
- Bioinformatics Forum
- BizTEC Forum
- CGGC Weekly Seminar
- Haifux, Haifa Linux Club
- Pixel Club
- Theory Seminar
Upcoming Colloquia & Seminars
Motion Planning in the Presence of Mobile Obstacles
- Avraham Stiefel, M.Sc. Thesis Seminar
- Sunday, 31.5.2015, 15:30
- Taub 401
- Prof. G. Barequet
We take a new approach to motion planning specifically designed for handling mobile obstacles. Previous methods are modified versions of the algorithms for static obstacles, but with speed-ups designed to ensure real-time operation. Because of this logic, each iteration requires a complete reconstruction of the path, based on the new locations of the robot and the obstacle. Ideally, the algorithm would consist of faster iterations that create a complete approximate path, but can re-use information so that our approximation improves during each iteration. We begin by performing a locally-optimal convex decomposition of the freespace. At each iteration, we update the decomposition so that concave regions are split, but neighboring regions that can be fused into a larger convex region are fused. We then construct a piecewise-linear path that passes from the robot to the target, such that the joins are on edges created by the convex decomposition. We then augment the path to a smooth curve with bounded curvature; the specific form of curve is not relevant, but we present a number of different methods. Once an initial path is constructed, we iteratively improve our path while updating the convex decomposition. To do so, we remove or add linear segments as the convex decomposition demands. We then adjust the locations of the segments joins on the dividing edge segments, so that the adjusted path is an approximation of the shortest path. We show that our method is computationally faster than pre-existing algorithms. Furthermore, we show that because of the structure of the algorithm we can more easily determine if the entire path avoids obstacles.
Pixel Club: Analysis of High-throughput Microscopy Videos: Catching Up with Cell Dynamics
- Tammy Riklin Raviv (EE, Ben Gurion University)
- Tuesday, 2.6.2015, 11:30
- EE Meyer Building 1061
In the talk I will present a novel framework for high-throughput cell lineage analysis in time-lapse microscopy images. The proposed algorithm ties together two fundamental aspects of cell lineage construction, namely cell segmentation and tracking, via a Bayesian inference of dynamic models. The proposed contribution exploits the Kalman inference problem by estimating the time-wise cell shape uncertainty in addition to cell trajectory. These inferred cell properties are combined with the observed image measurements within a fast marching (FM) algorithm, to achieve posterior probabilities for cell segmentation and association. An original idea for cell mitosis detection, which is not specific to a particular dataset and does not require training will also presented. Highly accurate results, with respect to the state-of-the-art, on different cell-tracking datasets were obtained.
TCE Guest Lecture: A Gentle Introduction to Scala Programming Language
- Martin Odersky (EPFL)
- Wednesday, 3.6.2015, 09:00
- Auditorium 1, CS Taub Bld.
Scala is a language that fuses functional and object-oriented programming in a practical package. It interoperates seamlessly with Java and its tools. Scala is now used in a rapidly increasing number of open source projects and companies. It provides the core infrastructure for sites such as Twitter, LinkedIn, Foursquare, Tumblr, and Klout.
Send your friends, your students, your colleagues, open to all! No prior Scala knowledge is required.
Attendance is free, please pre-register.
Processing Real-time Data Streams on GPU-Based Systems
- Uri Verner, Ph.D. Thesis Seminar
- Wednesday, 3.6.2015, 11:30
- Taub 337 (CeClub)
- Prof. Assaf Schuster and Prof. Avi Mendelson
Real-time stream processing of Big Data has an increasing demand in modern data centers. There, a continuous torrent of data, created from different streaming data-sources like social networks, video streams, and financial markets, is being processed and analyzed to produce valuable insights about its content, and, in some cases, their value has an expiration date. For example, in a silicon-wafer production inspection system, dozens of high-resolution cameras scan the wafer and generate high-rate streams of images, where defects as small as a pixel and even smaller are detected using image processing algorithms. The inspection is a computationally intensive task that must adhere to strict processing time limitations in order to keep up with the production line. High-end computing platforms, packed with CPUs and compute accelerators, are being used to deal with the large processing need. Optimizing such systems is a very challenging task because they are heterogeneous in both computation and communication. In this talk, I will present my PhD research work on the problem of processing multiple data streams with hard processing-latency bounds on multi-GPU compute nodes. The talk will describe the challenges in work distribution and communication scheduling in such a system, and present new methods that achieve higher utilization of the resources, while guaranteeing hard real-time compliance. The generalization of the previously discussed problems leads to an important new class of scheduling problems where processors affect each other's speed. To demonstrate its usefulness, a problem from this class is used to develop an efficient new scheduler that minimizes the makespan of compute jobs on Intel CPUs.
Theory Seminar: A Simple and Approximately Optimal Mechanism for an Additive Buyer
- Moshe Babaioff (Microsoft Research)
- Wednesday, 3.6.2015, 12:30
- Taub 201
We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer has a value for each item drawn independently according to (non-identical) distributions, and his value for a set of items is additive. The seller aims to maximize his revenue. It is known that an optimal mechanism in this setting may be quite complex, requiring randomization and menus of infinite size. Hart and Nisan have initiated a study of two very simple pricing schemes for this setting: item pricing, in which each item is priced at its monopoly reserve; and bundle pricing, in which the entire set of items is priced and sold as one bundle. Hart and Nisan have shown that neither scheme can guarantee more than a vanishingly small fraction of the optimal revenue. In sharp contrast, we show that for any distributions, the better of item and bundle pricing is a constant-factor approximation to the optimal revenue. We further discuss extensions to multiple buyers and to valuations that are correlated across items.
This paper is a joint work with Nicole Immorlica, Brendan Lucier and S. Matthew Weinberg
(Full paper available on-line at http://arxiv.org/abs/1405.6146)
Algorithmic Exam Generation
- Omer Geiger, M.Sc. Thesis Seminar
- Wednesday, 3.6.2015, 14:00
- Taub 601
- Prof. Shaul Markovitch
Given a class of students, and a pool of questions in the domain of study, what subset will constitute a ``good'' exam? Millions of educators are dealing with this difficult problem worldwide, yet the task of composing exams is still performed manually. In this work we present a novel algorithmic framework for exam composition. Our framework requires two input components: a student population represented by a distribution over a set of overlay models, each consisting of a set of mastered abilities, or actions; and a that, given any two student models, defines which should be graded higher. To determine the performance of a student model on a potential question, we test whether it satisfies a disjunctive action landmark, i.e., whether its abilities are sufficient to follow at least one solution path. Based on these, we present a novel utility function for evaluating exams. An exam is highly evaluated if it is expected to order the student population with high correlation to the target order. The merit of our algorithmic framework is exemplified with real auto-generated questions in the domain of middle-school algebra.
Augmenting 2D planar maps to 3D
- Nir Hershko, M.Sc. Thesis Seminar
- Sunday, 7.6.2015, 13:30
- Taub 337
- Prof. Gershon Elber
Maps of the world around us are used daily for many purposes such as navigation or location-based services. However, our experience with maps is usually limited to a 2D top-down projection. Using a 3D map instead have some advantages, such as easier navigation and orientation, more realistic modeling and simulation of natural phenomena such as water flow or line-of-sight analysis, and better understanding of the elevation differences. In this talk, we will present a few methods that can provide us with better 3D maps: - Augmentation of 2D road interchanges to 3D using GPS traces recorded while driving. - Refinement and amelioration of digital terrain models (DTMs) using GPS traces recorded in the area. - Estimating buildings' elevations using the accelerometers and magnetometers in smart-phones. We demonstrate these methods based on the map of the OpenStreetMap project, with the results visualized in 3D (http://osm3d.cs.technion.ac.il/). This talk summarizes the M.Sc. research of the speaker under the supervision of Prof. Gershon Elber.