
CS Colloquium 20122013  Fall Semester:
Coordinator: Prof. Haim Kaplan
Place: Schreiber 309
Time: 11:00 gathering, cookies and coffee
11:1512:15 colloquium talk

Date 
Speaker 
Title 
October 28 2012
11:15  12:15

Sivan Toledo


Open and RecentlyResolved Problems in Numerical Linear Algebra
We will be
looking at colorings of grids. A ccoloring of a grid is an assignment
toe every grid point a color. For example, this is a 2coloring of the
3 x 7 grid using colors R,B,G. rrbbbrr bbrbrbb rrrrbrb Note that there
is a rectangle with all four corners the same color (we use capital
letters to denote it) RrbbbRr bbrbrbb RrrrbRb If a grid can be
ccolored without a monochromatic rectangle we say that the grid is
ccolorable. Which grids can be 2colored? 3colored? 4colored? etc.
1) We have characterized EXACTLY which grids are 2colorable. 2) We
have characterized EXACTLY which grids are 3colorable. 3) We have made
porgress on EXACTLY which grids are 4colorable. 4) We have GIVEN UP on
trying to find EXACTLY which grids are 5colorable. The work is a
combination of some clever math and some computer work.

November 11 2012
11:1512:15

Anna Zamansky


Taming NonClassical Logics: Theory, Tools, Applications
In recent decades a vast variety of nonclassical logics have been introduced, driven by various CS applications. Temporal logics, separation logics, fuzzy logics and paraconsistent logics are just a few prominent examples, used in verification of software and hardware, medical expert systems, data and knowledge bases, etc. A useful logic should ideally have two components: a simple and intuitive semantics, which can provide real insights into the logic, and a corresponding analytic proof system which is the key to effective proof search strategies for automated deduction methods. Obtaining these components for a given logic is a challenging process, which is usually tailored to the particular logic at hand. However, due to the increasing number of new applicationdriven logics, there is a need for a systematic approach to obtaining these components, which could be used for developing tools for automatic support for the design and investigation of logical systems.
In this talk we show that this goal can be achieved at least for some useful families of nonclassical logics. We provide a uniform and modular method for a systematic generation of effective semantics and analytic proof systems for a very large family of paraconsistent logics used for reasoning with inconsistent information, thus making a substantial step towards the development of efficient paraconsistent theorem provers. The method, implemented by the Prolog system PARAlyzer, has been extended to infinitely many other logics formulated in terms of axiomatic systems of a certain natural form.
Joint work with (i) A. Avron and B. Konikowska, (ii) A. Ciabattoni, O. Lahav and L. Spendier

November 25 2012
11:1512:15 
Yuri Gurevich 

What is an Algorithm?
How can one possibly analyze computation in general? The task seems daunting if not impossible. There are too many different kinds of computation, and the notion of general computation seems too amorphous. As in quicksand, one needs a rescue point, a fulcrum. In computation analysis, a fulcrum is a particular viewpoint on computation that clarifies and simplifies things to the point that analysis become possible.
We review from that point of view the few foundational analyses of general computation in the literature: Turing's analysis of human computations, Gandy's analysis of mechanical computations, Kolmogorov's analysis of bitlevel computation in spacetime, and our own analysis of computation on the arbitrary abstraction level.

December 16 2012
11:1512:15 
Rotem Oshman 

New Connections Between Distributed Computing and Communication Complexity
The advent of largescale wireless networks has presented the distributed computing community with a new challenge: wireless networks are much more disorderly than traditional wired networks, and they are difficult to model and predict. In addition, they are subject to different design considerations: among other criteria, it is crucial to conserve power by reducing the amount of communication between network nodes. This communication constraint leads to interesting connections between distributed computing and communication complexity.
In this talk I will discuss the problem of computing some function of inputs to the nodes of the network (e.g., the average temperature measured in the network, the number of targets tracked, etc.). In traditional, wired networks, this class of problems is "solved": the optimal solution is to compute a spanning tree, then compute the function "up the tree". However, I will show that in wireless networks, finding a spanning tree is much harder, and consequently we are better off finding other ways to compute the function of interest.
To argue that finding a spanning tree is hard, I will introduce a new communication complexity problem called PARTITION, and prove a lower bound on its twoplayer communication complexity. I will then discuss the relationship to finding a spanning tree, and also describe a fast multiplayer algorithm for PARTITION. I will conclude the talk by describing recent work on a new model of communication complexity, aimed to more closely capture the nature of communication in a wireless network.

December 23 2012
11:1512:15

Ken Goldberg, UC Berkeley


Putting the Turing into Manufacturing:
Recent Developments in Algorithmic Automation
Automation for manufacturing today is where computer technology was in
the early 1960's, a patchwork of adhoc solutions lacking a rigorous
scientific methodology. CAD provides detailed models of part
geometry. What's missing is formal models of part behavior, frameworks
for the systematic design of automated systems that handle
(e.g. assemble, inspect, sort, feed) parts, and tools for rigorous
specification, analysis, and synthesis.
In 1937, Alan Turing introduced an elegant model of computing with
precise vocabulary and operations that formalized concepts of
equivalence, correctness, completeness, and complexity. Can we develop
similar models for manufacturing?
"Algorithmic Automation" introduces abstractions that allow the
functionality of automation to be designed independent of the
underlying implementation and can provide the foundation for formal
specification and analysis, algorithmic design, and consistency
checking. Algorithmic Automation can facilitate integrity,
reliability, interoperability, and maintainability and upgrading of
automation.
Researchers are developing a variety of algorithmic models. I'll
present results from my lab and others on specific problems in part
feeding and fixturing, including a framework for fixturing deformable
parts and new geometric primitives for vibratory bowl feeders, and
propose open problems for future research.

Januar 6 2013
11:1512:15

Tamir Hazan


Efficient Reasoning using Dual Decomposition and Random Maximum APosteriori Perturbations
Learning and inference in complex models drives much of the research in machine learning and computer vision. In a fully probabilistic treatment, all possible alternative assignments are considered thus requiring to estimate exponentially many assignments with their respective weights. To relax the exponential complexity we describe
two different approaches: Dual decomposition and random maximum aposteriori (MAP) perturbations. The second approach leads us to a new approximate inference framework that is based on MAPstatistics, thus does not depend on pseudoprobabilities, contrasting the current framework of dual decomposition. This approach excels in regimes where there are several but not exponentially many prominent assignments. For example, this
happens in cases where observations carry strong signals (local evidence) but are also guided by strong consistency constraints (couplings).

Januar 13 2013
11:1512:15

Mark Silberstein , Technion


Operating System Support for HighThroughput Processors
The processor landscape has fractured into latencyoptimized CPUs,
throughputoriented GPUs, and soon, custom accelerators. Future applications
will need to cohesively use a variety of hardware to achieve their performance
and power goals. However building efficient systems that use
accelerators today is incredibly difficult.
In this talk I will argue that the root cause of this complexity lies in
the lack of adequate operating system support for accelerators. While
operating systems provide optimized resource management
and Input/Output (I/O) services to CPU applications, they make no such
services available to accelerator programs.
I propose GPUfs  an operating system layer which enables access to files directly from programs
running on throughputoriented accelerators, such as GPUs.
GPUfs extends the constrained GPUascoprocessor programming model,
turning GPUs into firstclass computing devices with full file I/O support.
It provides a POSIXlike API for GPU programs, exploits parallelism for efficiency,
and optimizes for access locality by extending a CPU buffer cache into physical memories
of all GPUs in a single machine.
Using real benchmarks I show that GPUfs simplifies the development
of efficient applications by eliminating the GPU management complexity,
and broadens the range of applications that can be accelerated by GPUs.
For example, a simple selfcontained GPU program which searches for a set of strings in the entire
tree of Linux kernel source files completes in about third of the time of an
8CPUcore run.
Joint work with Idit Keidar (Technion), Bryan Ford (Yale) and Emmett Witchel
(UT Austin).

March 10 2013
11:1512:15

Vadim Indelman


Incremental light bundle adjustment for structure from motion (SfM) and robotics
Fast and reliable bundle adjustment is essential in many structure from motion (SfM) related applications such as mobile vision, augmented reality and robotics. While much progress has been made in recent years to efficiently incorporate incoming imagery information, highrate performance is still a challenge, especially when operating in largescale environments over long time durations and in presence of loop closures, i.e. reobserving 3D points at different time instances, potentially from different viewpoints. In this talk, an incremental and computationally efficient method for bundle adjustment will be presented. The method incorporates two key ideas to substantially reduce the involved computational cost, compared to a conventional bundle adjustment. First, the cost function is formulated in terms of multiview constraints instead of projection equations, thereby algebraically eliminating the 3D structure from the optimization. If required, the observed 3D points, or any part of them, can be reconstructed based on the optimized camera poses. A formulation with threeview constraints is presented. As opposed to applying only epipolar geometry constraints, this formulation allows a consistent motion estimation also when the camera centers are colinear, a configuration commonly encountered in mobile robotics. The second component is the recently developed incremental smoothing approach, which adaptively identifies the variables that need to be recomputed at each step. The optimization problem is formulated in terms of a graphical model, a factor graph, and it is shown how to perform an efficient inference that typically involves only a fraction of the camera poses and fully exploits sparsity of the system. The latter has a major impact on the computational complexity of the method, which will be discussed and compared to stateoftheart bundle adjustment techniques.
In the final part of the talk, an approach that parallelizes computations to maintain highrate performance in presence of loop closure observations will be outlined. While existing related methods, such as PTAM and DTAM, relocalize the camera pose based on a map that is updated in a parallel process, the presented approach allows also a probabilistic integration of information from additional sensors, such as inertial sensors. 
April 7 2013
11:1512:15 
Dmitry Sotnikov, IBM 

To Zip or not to Zip: Effective Resource Usage for RealTime Compression
Realtime compression for primary storage is quickly becoming widespread as data continues to grow exponentially, but adding compression on the data path consumes scarce CPU and memory resources on the storage system.
In this talk I'll present different approaches to efficient estimation of the potential compression ratio of data and how these methods can be applied in advanced storage systems. Our work targets two granularities: the macro scale estimation which is backed up by analytical proofs of accuracy, and the micro scale which is heuristic.
Based on joint work with Danny Harnik, Oded Margalit, Ronen Kat, and
Avishay Traeger, from IBM Research  Haifa. This work has recently appeared in FAST 2013.

April 21 2013
11:1512:15 
Livnat Jerby 

Mining largescale genomic data to identify new selective cancer drugs
Conservative anticancer treatments harm both cancer and normal cells. To selectively target cancer cells while sparing normal cells one can harness the concept of synthetic lethality. Two genes constitute a Synthetically Lethal (SL) pair if although none of them is essential by itself for cell survival, cells cannot survive without both genes together. Unlike normal cells, cancer cells often lack certain genes. Targeting the SLpartner of a gene that has been lost in the cancer hence offers a selective treatment. The premise of our approach is the observation that cancer cells missing both SLpaired genes are selected against. Utilizing the latter, we identified SL interactions by analyzing genetic profiles of cancer clinical samples, and constructed the first genomescale Cancer SL Network (CSLN). The network enabled us to correctly predict effective treatments for different types of cancer, significantly matching existing experimental data. Going beyond current knowledge, our approach paves the way for developing new anticancer therapies with fewer side effects and improved therapeutic efficacy. Lastly, we describe SLbased treatment strategies that can mitigate the selection of cancer cells that are resistant to the treatment and hence reduce relapses.
[Joint work with Adam Weinstock, Tamar Geiger & Eytan Ruppin]

May 5 2013
11:1512:15 
Michal Armoni, Weizmann Institute 

Reduction as a habit of mind in computer science
The research presented in this talk is within the discipline of computer science (CS) education. This is a subfield of mathematics and science education, which in turn is a subfield of the discipline of education. Thus, research in CS education is based on methodologies of social science, as well as on understanding the special nature of CS – as a discipline that has something in common with mathematics, science and engineering, but also has unique characteristics of its own. The research of CS education focuses on two educational processes: the teaching process (what should we teach our students in order to better prepare them to be CS graduates, and how should we teach it?), and the learning process (how do our students interpret and perceive what we teach them?).
I intend to describe a series of studies (some are joint work with Judith GalEzer and Orit Hazzan) that focus on reduction. Reduction, in a generalized interpretation, can be viewed as a CS habit of mind, a problemsolving strategy that is relevant to many CS areas. CS educators often assume that CS graduates learn to appreciate this strategy and work with it. However, our findings indicate difficulties that CS undergraduate students have with reduction. Some of these difficulties are rooted in the fact that reduction is strongly related to abstraction. Specifically, our findings indicate difficulties that undergraduate students (even advanced students) have with the black boxes.

May 19 2013
11:1512:15 
Amir Herzberg, Bar Ilan University 

OffPath Hacking: The Illusion of ChallengeResponse Authentication
Everyone is concerned about Internet security, yet most traffic is not cryptographically protected. The usual justification is that most attackers are only {\em offpath} and cannot intercept traffic; hence, challengeresponse mechanisms suffice to ensure authenticity. Usually, the challenges reuse existing `unpredictable' protocol header fields; this allows use of existing, widelydeployed protocols such as TCP and DNS.
We argue that this practice may only give an {\em illusion of security}. We present our recent offpath TCP injection and DNS poisoning attacks, allowing circumvention of existing challengeresponse defenses.
Both TCP and DNS attacks are nontrivial, yet very efficient and practical. The attacks allow circumvention of widely deployed security mechanisms, such as a Same Origin Policy, and allow a wide range of exploits, e.g., longterm caching of malicious objects and scripts.
We hope that this article will motivate adoption of cryptographic mechanisms such as SSL/TLS, IPsec and DNSSEC, as well as of correct, secure challengeresponse mechanisms.
The talk would be mostly selfcontained.
(Joint work with Yossi Gilad and Haya Shulman)

May 26 2013
11:1512:15 
HelOr Yacov, IDC Herzeliya 

Matching by Tone Mapping
Fast pattern matching in images, termed Matching by Tone Mapping (MTM) is
introduced which allows matching under nonlinear tone mappings. We
utilize the Slice Transform to implement a fast computational scheme requiring
computational time similar to the fast implementation of Normalized Cross Correlation (NCC).
In fact, we show that the MTM measure can be viewed as a generalization of the NCC for nonlinear
mappings. MTM bears a close similarity to the Mutual Information but is more robust in extreme scenarios.
If time permits, I’ll show that MTM can be formulized as a graph Laplacian where pattern’s pixels are
represented by a weighted graph. Generalizing the Laplacian distance results in distance measures which
are tolerant to various visual distortions.

June 2 2013
11:1512:15 
Dr. Gabi Siboni 

בין מדעי המחשב לבטחון הלאומי – הזדמנויות חדשות ומרתקות במחקר הבין תחומי
המכון למחקרי ביטחון לאומי נוסד באוקטובר 2006 והוא משלב בתוכו את מרכז יפה למחקרים אסטרטגיים, שנוסד והוקם באוניברסיטת תל אביב, ב1977. המרכז שימש פורץ דרך בישראל בהגדירו את תחום לימודי הביטחון ובכך שמיסד את סוגיית ההגנה והביטחון הלאומי כתחומי מחקר. המכון הוא אמפלגתי, בלתי תלוי, ועצמאי בהשקפות המובאות במחקריו. כמכון חיצוני של אוניברסיטת תל אביב, שומר המכון על קשר אמיץ עם סביבתו האקדמית ובמקביל, מקיים קשרי עבודה עם הממסד הפוליטי והצבאי.
תכנית לוחמת סייבר במכון למחקרי בטחון לאומי שמה לה למטרה לפתח את הידע ולהעמיק את הדיון והתובנות בנושא הסייבר מתוך מטרה להעניק להנהגה בישראל יכולות משופרות להתמודדות עם איום חמור זה בתהליכי קבלת ההחלטות.
לסטודנטים בתחום מדעי המחשב הזדמנויות רבות להשתלב במחקר הזה ולהגדיל דרכו הקשרים, והאפשרויות להשתלב בשוק העבודה עם יתרון יחסי ייחודי. שעיקרו: השילוב שבין מדעי המחשב ללימודי הבטחון.
הסמינר יציג את האפשרויות השונות העומדות בפני הסטודנט ואת ההזדמנויות הנגזרות מכך.




Linear programming (LP) and semidefinite programming (SDP) are
powerful convex optimization tools which have become ubiquitous in the
field of approximation algorithms in the last few decades. Given a
combinatorial optimization problem (e.g. Maximum Independent Set), the
standard approach to obtain an approximation algorithm is as follows:
formulate the problem as an integer program (IP), relax this
formulation to an LP or SDP (these can be solved efficiently), find
the optimum solution of the relaxation, and then "round" the solution
back to an integer solution.
This approach is limited by how well the convex program (LP or SDP)
approximates the original IP formulation. One way to circumvent this
limitation is through hierarchies of convex programs, which give a
systematic way of iteratively strengthening any relaxation (at the
cost of increased running time to solve it), so that the gap between
the relaxation and the original IP gradually decreases.
Unfortunately, most of the literature on hierarchies in the context of
approximation algorithms has focused on impossibility results. Despite
this initial pessimistic trend, there has been a surprising surge of
recent positive results. I will survey some of these recent
developments through a number of examples of combinatorial
optimization problems for which we have been able to achieve improved
approximations using hierarchies.




Finding and fixing concurrency bugs is critical in modern software systems.
This talk examines two recent efforts to automate both the detection and
the repair of certain types of concurrency bugs using a mixture of static,
dynamic, and statistical methods.
First, we present a lowoverhead instrumentation framework to diagnose
productionrun failures caused by concurrency bugs. We track specific
thread interleavings at runtime, using sparse random sampling to limit
overhead. Methods drawn from work in statistical debugging let us identify
strong failure predictors among the sampled concurrent behaviors. Our
approach offers a spectrum of performance and diagnosis capabilities
suitable for wide deployment to real user desktops.
Second, we describe a strategy for automatically fixing one of the most
common types of concurrency bugs in realworld code. Starting with
descriptions of bad interleavings, our tool automatically inserts
synchronization operations to steer future executions away from danger.
Static analyses help us maintain good performance while reducing the risk
of deadlocks. Dynamic monitoring allows for runtime recovery from
deadlocks that could not be statically avoided. Overall, our approach
yields overheads too low to reliably measure; produces small, simple,
understandable patches; and completely eliminates detected bugs in the
targeted class across a variety of complex, realworld applications




NP contains
all those problems that we could efficiently solve if "guessing were
free", i.e., all those problems whose solutions we could recognize as
correct if they were given to us in an appropriate format and context.
We've known since 1971 that a large class of important combinatorial
problems including boolean satisfiability (SAT) are NP complete, i.e,
hardest problems in NP. If any of these had a solution in P, then so
would all other problems in NP. How hard is SAT, or any other
NPcomplete problem? It is well believed that P is not equal to NP and
that SAT requires exponential time on some hard instances. However, SAT
solvers are now in practical use as general problem solvers, currently
working even on instances with a million variables. I will explain some
of these issues, laying out what we do know, what we do not know, and
what we hope to understand once the P versus NP question, together with
many similar but less famous open questions, are finally resolved. At
the same time, this talk will present a survey of descriptive
complexity  the logical approach to complexity that I have been
pursuing for years




Over the past
decade, machine learning has emerged as a major and highly influential
discipline of computer science and engineering. As the scope and
variety of its applications increase, it faces novel and increasingly
challenging settings, which go beyond classical learning frameworks. In
this talk, I will present two recent works which fall under this
category. The first work introduces a new model of sequential decision
making with partial information. The model interpolates between two
wellknown online learning settings ("experts" and multiarmed
bandits), and tradesoff between the information obtained per round and
the total number of rounds required to reach the same performance. The
second work discusses the problem of parallelizing gradientbased
learning algorithms, which is increasingly important for webscale
applications, but is highly nontrivial as these algorithms are
inherently sequential. We show how this can be done using a generic and
simple protocol, prove its theoretical optimality, and substantiate its
performance experimentally.


































































































CS Colloquium 20122013  Spring Semester:


