# Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.

## Upcoming Colloquia & Seminars

• ### Theory Seminar: Playing Non-linear Games with Linear Oracles

Speaker:
Dan Garber (Technion)
Date:
Wednesday, 11.12.2013, 12:30
Place:
Taub 201

Online Learning deals with playing repeated games against an adversary with the aim of minimising a quantity known as regret, and has attracted much attention in recent years due to its applications in algorithm design and machine learning. The computational bottleneck in the application of online learning algorithms is the computation of a projection of a point onto a convex set, which for many problems of interest, such as those that arise in combinatorial optimization and matrix optimization, is prohibitive. An alternative approach is to design algorithms for online learning that trade expensive projection steps in favour of linear optimization steps over the feasible domain, which for many problems are much more efficient and simple to implement.

In this talk we will present an algorithm for online learning that uses only linear optimization steps over the feasible domain (one per iteration of the game) and attains optimal regret, resolving an open question by Vempala and Kalai (COLT 2003), and Hazan and Kale (ICML 2012), in case the feasible domain is a polytope.

Our method is based on a novel variant of the conditional gradient method, that reduces the task of minimizing a smooth convex function over a domain to that of minimizing a linear objective. Whereas previous variants of this method give rise to approximation algorithms, we give such algorithm that converges exponentially faster.

The talk is based on a joint work with Elad Hazan (FOCS '13).

• ### Randomized Algorithms for Faster Linear and Non-linear Regression

Speaker:
Haim Avron - CS-Lecture - Note unusual day
Date:
Wednesday, 11.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131211_14_30_Avron.html
• ### How Can we Recover from Protocol Failure? (Talk II - The Israel Pollak Distinguished Lecture Series)

Speaker:
Ross Anderson (Computer Laboratory, University Of Cambridge)
Date:
Thursday, 12.12.2013, 11:00
Place:
Room 337-8 Taub Bld.

Security protocols are the foundations on which the digital age is built. SSL/TLS is the basis for online commerce, email privacy and much else; EMV is taking over the world of card payments; and lesser-known protocols such as SSH and DNSSEC protect the infrastructure. Stable, reliable platforms are the basis on which others can innovate; but what happens when the platforms themselves fail? We have so far seen about a dozen failures of SSL/TLS, and had to patch them in very ad-hoc ways because it is not feasible to replace whole ciphersuites quickly, or even to change the clients and the servers at the same time. There has been a whole series of attacks on EMV, many of which are still not really patched. And now we find, pace Snowden, that many protocols have been the subject of deliberate attempts to weaken them; we are dealing not just with bugs and blunders but with adversarial behaviour. One of the most challenging problems we face is how to repair broken protocols when some of the participants are obstructive; we may have to move beyond protocol analysis and security-economic analysis to think in terms of strategy, politics and even diplomacy. A related problem is how to design protocols that will be as resilient as possible against future adversarial behaviour.

Bio:
Ross Anderson is Professor of Security Engineering at Cambridge University. He holds a Brandeis award for lifetime achievement in health privacy; he has worked for the British and Icelandic medical associations, been a special advisor to the UK parliament's health committee, and was an author of "Database State" – a report that led the UK government in 2010 to cancel two large systems to collect data on children. He has made a number of technical contributions to security, from cryptography through hardware tamper-resistance to API security; and he is one of the founders of security economics, which brings the tools of game theory and microeconomic analysis to bear on complex multistakeholder systems.

• ### Rank Modulation for Flash Memory

Speaker:
Michal Horovitz, M.Sc. Thesis Seminar
Date:
Thursday, 12.12.2013, 11:30
Place:
Taub 701
Prof. Tuvi. Etzion

Snake-in-the-box code is a Gray code which is capable to detect a single error. Gray codes are important in the context of rank modulation scheme which was suggested recently for representing information in flash memories. For a Gray code in this scheme the codewords are permutations, two consecutive codewords are obtained by using the "push-to-the-top" operation, and the distance measure is defined on permutations. In this talk the Kendall's $\tau$-metric is used. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length $((2n+1)2n-1) M$ for permutations of $S_{2n+1}$ from a snake of length $M$ for permutations of $S_{2n-1}$. We present a direct construction based on necklaces which might yield snakes of length $\frac{(2n+1)!}{2}-2n+1$ for permutations of $S_{2n+1}$. The construction is applied successfully for $S_7$ and $S_9$.

• ### CGGC Seminar: Multi-view Inter-media: From Space to Ocean-depths

Speaker:
Yoav Y. Schechner (EE, Technion)
Date:
Sunday, 15.12.2013, 13:00
Place:
Room 337-8 Taub Bld.

This talk is about ;multi-view imaging via participating media, particularly the 3D volumetric scattering atmosphere and the 3D wavy water-air interface. Camera multi-views are either looking down from outer-space, or looking up from underwater or the ground level.  Multiple views on scales of tens or hundreds of kilometers effectively create a huge lightfield camera-system. This provides constraints for recovering complex scenes, including the 3D distribution of aerosols overhead, or underwater topography. On a small scale, multiple submerged cameras viewing via random water-surface waves create a 'virtual periscope': it stochastically localizes objects in open air, without revealing the viewer. This may have implications to some marine animals.

See more at:

• ### Lower Bounds for Linear Decision Trees via An Energy Complexity Argument

Speaker:
Eiji Takimoto - CSpecial Lecture - Note unusual day and place
Date:
Monday, 16.12.2013, 14:30
Place:
Room 701 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131216_14_30_Takimoto.html
• ### T2med: Social-Mobile-Cloud Meets Medicine @ Technion

Date:
Tuesday, 17.12.2013, 08:30
Place:
Kogan Auditorium, EE Meyer Building

You are ivnited to the T2med Conference on Social-Mobile-Cloud Meets Medicine @ Technion, organizerd by Deborah Estrin (CS, Cornell NYC Tech), Shie Mannor (EE, Technion), Uri Rosenschein (Medical School, Technion)

The conference will be held on Tuesday, December 17th, 2013

The world around us has been transformed by the brave new world of Social (networks) – Mobile (smart phones). The phenomenon of ubiquitous programmable, hand held sensor platforms (our phones), streaming continuous and diverse personal information to be stored and analyzed in the "cloud" has already transformed how we run our lives, and will soon transform how we take care of our lives. The ability to use intelligent algorithms to draw inferences from these data, to fuse them with other data (from genomic to geospatial), and to connect even more sensors to these devices, offers tremendous opportunity for data driven insight into patient care across a wide array of health conditions.
The objective of the meeting is to bring together innovators from both IT and Medicine and explore the potential implication of the social-mobile-cloud reality on patient care.

Confirmed Speakers

Offer Fabian (Medial)
Uri Goren (e-pochondriac)
Jonathan Javitt (Telcare)
Eyal Lifshitz (Peregrine)
Avi Mandelbaum (Technion)
Gideon Mantel (Treato)
Joachim Meyer (Tel Aviv University)
Avi Mendelson (Technion)
Ariel Miller (Technion)
Eben Moglen (Columbia University)
Mor Peleg (Haifa University)
Eliezer Shalev (Technion)
Lior Wolf (Clalit Health Service)
Benny Zeevi (IATI)

Participation requests pre-registration. More details and agenda

• ### Predicate Abstraction For Relaxed Memeory Model

Speaker:
Yuri Meshman, M.Sc. Thesis Seminar
Date:
Tuesday, 17.12.2013, 11:30
Place:
Taub 601
Prof. E. Yahav

In this talk we present a novel approach for predicate abstraction of programs running on relaxed memory models. Our approach consists of two steps. First, we reduce the problem of verifying a program P running on a memory model M to the problem of verifying a program P_M that captures an abstraction of M as part of the program. Second, we show how to discover new predicates that enable verification of P_M. The core idea is to extrapolate from the predicates used to verify P under sequential consistency. A key new concept is that of cube extrapolation: it successfully avoids exponential explosion when abstracting P_M. We implemented our approach for the x86 TSO and PSO memory models and showed that predicates discovered via extrapolation are powerful enough to verify several challenging concurrent programs. We show that our cube extrapolation approach introduces a x100 reduction in the number of SMT calls for several programs, enabling their verification. This is the first time some of these programs have been verified for a model as relaxed as PSO.

• ### Pixel Club: Video Saliency and its Applications in Single and Multi-camera Setups

Speaker:
Dmitry Rudoy (Technion)
Date:
Tuesday, 17.12.2013, 11:30
Place:
EE Meyer Building 1061

Understanding human attention have interested researchers for decades. The early works come from different fields of psychology and separate the cognitive process into several steps. The different models of attention in static scenes have emerged and evolved into dynamic saliency. Along with that, there are extensive cinematographic theories on how the scene should be watched, or filmed. And again, there is a long term research interest in view selection for static and dynamic scenes. Different methods propose how to place a camera in a scene and how to move it. The central contribution of this research is a novel approach to video saliency modeling. We propose a model that can effectively predict humans' attention in any particular video. The system is learn from human examples, so our second contribution is an effective method for massive collection of gaze data. We adapt our model to multiple camera scenarios by proposing an approach for view selection based on fixed cameras. As the last contribution we propose a method to shift human attention by inlaying artificial objects into a video. Our model for video saliency is based on modeling gaze as attention shifts between consecutive video frames. This is different from analyzing each image independently, as was often done before and allows us to maintain temporal stability of the saliency maps. We incorporate static, motion and semantic features from the video to propagate a saliency map from one frame to another. We show that this model is better to the behavior of the human eyes. Since our saliency model is learn from a large database of human gaze tracks we additionally propose a method to collect them from any number of participants. The method employs crowdsourcing technique and allows to record gaze location on any number of frames of any video. Opposite to the traditional gaze tracking methods, our method does not require any special equipment and participants are not limited by any geography or culture.

As an approach to multiple camera setups we propose a method for efficient viewpoint selection from any set of cameras that view the same scene. As placing a camera at specified place usually requires knowledge of 3D data our method works with fixed cameras. It is capable of ranking the cameras according to the visibility of the actions happening in the scene. After the best view is selected the video saliency method can be applied to the resulting set of frames.

We further wish to edit the input video and shift the humans' attention. To do so we propose a user-friendly system for seamless inlaying of any 3D object into any video. We model the video as a single image, ask the user to add the object in the desired place and then render it back to the video.

To verify the proposed methods we test them on known video datasets and on real-life videos. We compare our results quantitatively to the state-of-the-art methods and outperforms them. Additionally, we present qualitative tests that render our results more visually appealing that the previous approaches.

• ### New Approaches to Graph Partitioning

Speaker:
Roy Schwartz - CS-Lecture
Date:
Tuesday, 17.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131217_14_30_Schwartz.html
• ### Practical Concurrent Binary Search Trees via Logical Ordering

Speaker:
Dana Drachsler, M.Sc. Thesis Seminar
Date:
Wednesday, 18.12.2013, 12:30
Place:
Taub 701
Prof. E. Yahav

In this talk, we present novel practical concurrent binary search tree (BST) algorithms based on the following general idea: we explicitly maintain logical ordering information in the data structure, permitting clean separation from its physical tree layout. We capture logical ordering using intervals, enabled by the following key observation: any set of totally ordered items can be uniquely partitioned into logical interval ranges with the property that an item belongs to the set if and only if the item is an endpoint of some interval. These ideas enable us to construct efficient, synchronization-free and intuitive lookup operations. Specifically, we present: (i) A concurrent non-balanced BST with a lock-free lookup, and (ii) A concurrent AVL tree with a lock-free lookup which proceeds without synchronizing with any mutating operation, including balancing operations.

• ### Theory Seminar: Theoretical Computational Tools at the Service of Constructing the Big Tree of Life

Speaker:
Sagi Snir (Haifa University)
Date:
Wednesday, 18.12.2013, 12:30
Place:
Taub 201

The reconstruction of evolutionary trees is a fundamental task in Biology. The exponentially increasing amount of available genomic date over thousands of genes and species, gave rise to the task of combining all this data for the sake of constructing a phylogeny (evolutionary tree) depicting the evolution of life on earth along several billions of years.

Since accurate reconstruction is limited to few dozens of species, the supertree approach, aims at accurately reconstructing small trees over overlapping species sets and subsequently amalgamate these trees into a single tree over the full set of species.

A quartet tree, a tree over four species, is the simplest piece of phylogenetic information. Hence, the supertree problem when all input trees are quartet trees, is the simplest version of this task that is still widely applicable, yet quite challenging. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, the problem of dealing with conflicting quartet set or even with arbitrary congruent set remained open where the best known approximation ratio is $\frac{1}{3}$, obtained naively by a random tree.

In a series of works we have developed a graph theoretically based approach for the quartet supertree task. Our approach is based on a divide and conquer algorithm where our divide step uses a semi-definite programming (SDP) formulation of MaxCut in a graph representing relationships between the species. We could show several approximation bounds using this approach for a wide variety of inputs, that improves substantially the $\frac{1}{3}$ bound for general inputs. We also derived negative results regarding the information encompassed in quartet subsets, over the full quartet set.

Based on joint works with Satish Rao, Raphy Yuster, and Noga Alon.

The talk is self-contained and requires no prior knowledge in Biology.

• ### A Relational Framework for Information Extraction

Speaker:
Benny Kimelfeld - CS-Lecture - Note unusual day
Date:
Wednesday, 18.12.2013, 14:30
Place:
Room 337 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131218_14_30_Kimelfeld.html
• ### Aspects of Formal Verification

Date:
Thursday, 19.12.2013, 08:30
Place:
Room 337-8 Taub Bld.

You are invited to a special Symposium on "Aspects of Formal Verification" on the occasion of Prof. Shmuel Katz' retirement. The symposium will be held on Thursday, December 19 2013, at Taub Building for Computer Science, in room 337 (3rd floor).

Participation is free but requires pre-registraion.

You are all invited.

More details and program.

• ### Polynomial Bounds for the Grid-Minor Theorem

Speaker:
Julia Chuzhoy - CSpecial Lecture-Note unusual time and place
Date:
Thursday, 19.12.2013, 13:30
Place:
Room 601 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131219_13_30_Chuzhoy.html
• ### Privacy by Diversity in Sequential Releases of Databases

Speaker:
Erez Shmueli - CS-Lecture
Date:
Sunday, 22.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131222_14_30_Shmueli.html
• ### Learning with Lower Information Costs

Speaker:
Sivan Sabato - CS-Lecture - Note unusual day
Date:
Wednesday, 25.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131225_14_30_Sabato.html
• ### Population Recovery and Partial Identification

Speaker:
Avi Wigderson - Colloquium Lecture
Date:
Thursday, 26.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131226_14_30_Wigderson.html
• ### Shortest Path Queries: Static, Dynamic and Fault-tolerant.

Speaker:
Shiri Chechik - CS-Lecture
Date:
Sunday, 29.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131229_14_30_Chechik.html
• ### Toward Better Depth Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Speaker:
Or Meir - CS-Lecture
Date:
Tuesday, 31.12.2013, 14:30
Place:
Room 337-8 Taub Bld.
http://www.cs.technion.ac.il/~colloq/20131231_14_30_Meir.html
• ### On kinetic Delaunay triangulations

Speaker:
Natan Rubin - CS-Lecture
Date:
Sunday, 5.1.2014, 14:30
Place:
Room 337-8 Taub Bld.