
CS Colloquium 20112012  Fall Semester:
Coordinator: Dr. Iftach Haitner
Place: Schreiber 006
Time: 11:00 gathering, cookies and coffee
11:1512:15 colloquium talk

Date 
Speaker 
Title 
October 30 2011
14:0015:00 * special date and time 14:0015:00 
Bil Gasarch 

When can you color a grid and not have any monochromatic rectangles
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 6 2011
11:1512:15 
Amir Herzberg 

Internet Security: Still Vulnerable After All These Years
The Internet is thriving, but, in spite of its wide use and
importance, it still suffers from alarming security vulnerabilities  some
even in the basic standards such as DNS, TCP and IP, which are wellknown
since the 1980s.
This results in growing threats to individuals, corporations, and national
security. In this article, we briefly discuss three major challenges to
Internet security:
{\em software challenges}, {\em usability challenges} and {\em protocol
challenges}.
We demonstrate each of the three challenges by discussing past and current
failures, and outline some promising directions.
We hope that the discussion will raise awareness and motivate research,
development and adoption of improved security systems.

November 13 2011
11:1512:15 
David F. Bacon 

Liquid Metal: Programming in the Age of Heterogeneous Machines
The end of frequency scaling means that the search for performance must turn
elsewhere, and will inevitably require improvements in transistor efficiency
that can only be obtained by specializing hardware to programs. So begins the
age of heterogeneous machines.
The goal of the Liquid Metal project at IBM Research is to enable the use of these
heterogeneous machines by providing a single programming language that can be
compiled, executed, and dynamically migrated across a very diverse set of
systems: CPUs, GPUs, reconfigurable hardware (FPGAs), Cellstyle processors,
etc.
Achieving this goal requires significant innovation across the entire system:
language design, compiler technology, interactive development environment,
debugging, hardware synthesis, the runtime system, performance analysis,
and hardware protocols.
I will give an overview of the Liquid Metal language and the system we have
built, demonstrate dynamic execution across multiple platforms, present some
initial performance results, and describe challenges for the future.
Joint work with Joshua Auerbach, Perry Cheng, Stephen Fink, Rodric Rabbah,
Sunil Shukla (IBM Research), Yu Zhang (IBM China), and Christophe Dubach
(U. Edinburgh). 
November 27 2011
11:1512:15 
Eden Chlamtac 

Convex Programming Hierarchies: Trading Time for Approximation
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. 
Deceember 4 2011
11:1512:15 
Ben Liblit 

Internet Security: Still Vulnerable After All These Years
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 
December 11 2011
11:1512:15 
Neil Immerman 

"P versus NP: Approaches, Rebuttals, and Does It Matter?"vent
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 
December 18 2011
11:1512:15 
Ohad Shamir 

Machine Learning: Higher, Faster, Stronger
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. 
December 25 2011
11:1512:15 
Hanuka (no lecture) 


January 1 2012
11:1512:15 
Keren CensorHillel


Fast Distributed Computing Despite Poor Connectivity
Distributed computing is becoming the predominant form of computation and
communication world round, from cell phones to multicore machines. As
these systems grow in size, they become distributed, attempting to maintain
global computation and coordination despite ever weaker local guarantees.
This talk will address distributed computing in the Gossip model, where
each node in a network is restricted to contacting only a single neighbor
in each round of communication. I will show that any algorithm that
requires T rounds in the Local model (where each node contacts all
neighbors in each round) can be simulated in O(T+polylog(n)) rounds in the
GOSSIP model, implying that these two models of distributed computation are
essentially equivalent.
The main result that leads to this simulation is an algorithm for the
Gossip model in which each node exchanges information (perhaps indirectly)
with each of its neighbors within a polylogarithmic number of rounds. This
holds for every graph, despite the possibility of large degrees. A key
ingredient in this algorithm is a recursive decomposition of graphs into
clusters of sufficiently large conductance, allowing fast exchange of
information between nodes inside clusters and between clusters. To convert
the multiplicative polylogarithmic overhead for each simulated round into
the additive overhead in the final simulation result, I show connections
between sparse graph spanners and algorithms in the Gossip model. This
allows to simulate known constructions of nearlyadditive sparse spanners,
which can be used for even more efficient communication. 
January 8 2012
11:1512:15 
Yuval Emek 

Cutting edge(s) distributed computing
The theory of distributed computing, which lies at the heart of understanding the power and limitations of distributed systems, underwent tremendous progress over the last few decades.
Despite this progress, there seems to be a widening gap between the traditional models on top of which the theory of distributed computing is built and the realworld problems we wish to investigate through these models.
In this talk we will examine the different aspects of this widening gap and present some of the efforts made in attempt to adjust the field of theoretical distributed computing to the rapidly changing needs of its practical applications.
In particular, we will discuss the necessity to relax the dependency on rigid graphbased models in distributed computing, focusing on recent advances in the study of wireless networks and on a new model for decentralized networks of “unorthodox” devices.
The talk will be selfcontained. 
January 15 2012
11:1512:15 
Roi Reichart 

Efficient and Exact InterSentence Decoding for Natural Language Processing
A fundamental task in Natural Language Processing (NLP) is learning
the syntax of human languages from text.
The task is defined both in the sentence level ("syntactic parsing")
where a syntactic tree describing the headargument structure is to be
created,
and in the word level ("partofspeech tagging") where every word is
assigned a syntactic category such as noun, verb, adjective etc.
This syntactic analysis is an important building block in NLP
applications such as machine translation and information extraction.
While supervised learning algorithms perform very well on these tasks
when large collections of manually annotated text (corpora) exist,
creating manually annotated corpora is costly and error prone due to
the complex nature of annotation. Since most languages and text genres
do not have
large syntactically annotated corpora, developing algorithms that
learn syntax with little human supervision is of crucial importance.
The work I will describe is focused on learning better parsing and
tagging models from limited amounts of manually annotated training
data.
Our key observation is that existing models for these tasks are
defined at the sentence level, keeping inference tractable at the cost
of discarding intersentence information.
In this work we use Markov random fields to augment sentencelevel
models for parsing and partofspeech tagging
with intersentence constraints. To handle the resulting inference
problem, we present a dual decomposition algorithm
for efficient, exact decoding of such global objectives. We apply our
model to the lightly supervised setting and show
significant improvements to strong sentencelevel models across six
languages.
Our technique is general and can be applied to other structured
prediction problems in natural language processing
and in other fields, to enable inference over large collections of data.
Joint work with Alexander Rush, Amir globerson and Michael Collins. 
January 22 2012
11:1512:15 
Joseph Keshet 

Making Computers Good Listeners
A typical problem in speech and language processing has a very large
number of training examples, is sequential, highly structured, and has a
unique measure of performance, such as the word error rate in speech
recognition, or the BLEU score in machine translation. The simple binary
classification problem typically explored in machine learning is no longer
adequate for the complex decision problems encountered in speech and
language applications. Binary classifiers cannot handle the sequential
nature of these problems, and are designed to minimize the zeroone loss,
i.e., correct or incorrect, rather than the desired measure of performance.
In addition, the current stateoftheart models in speech and language
processing are generative models that capture some temporal dependencies,
such as Hidden Markov Models (HMMs). While such models have been immensely
important in the development of accurate largescale speech processing
applications, and in speech recognition in particular, theoretical and
experimental evidence have led to a widespread belief that such models
have nearly reached a performance ceiling.
In this talk, I first present a new theorem stating that a general
learning update rule directly corresponds to the gradient of the desired
measure of performance. I present a new algorithm for phonemetospeech
alignment based on this update rule, which surpasses all previously
reported results on a standard benchmark. I show a generalization of the
theorem to training nonlinear models such as HMMs, and present empirical
results on phoneme recognition task which surpass results from HMMs trained
with all other training techniques.
I will then present the problem of automatic voice onset time (VOT)
measurement, one of the most important variables measured in phonetic
research and medical speech analysis. I will present a learning algorithm
for VOT measurement which outperforms previous work and performs near human
interjudge reliability. I will discuss the algorithm’s implications for
telemonitoring of Parkinson’s disease, and for predicting the
effectiveness of chemoradiotherapy treatment of head and neck cancer.
Bio:
Joseph Keshet received his B.Sc. and M.Sc. degrees in Electrical
Engineering in 1994 and 2002, respectively, from Tel Aviv University. He
received his Ph.D. in Computer Science from The School of Computer Science
and Engineering at The Hebrew University of Jerusalem in 2007. From 1995 to
2002 he was a researcher at IDF, and won the prestigious Israeli award,
"Israel Defense Prize", for outstanding research and development
achievements. From 2007 to 2009 he was a postdoctoral researcher at IDIAP
Research Institute in Switzerland. From 2009 He is a research assistant
professor at TTIChicago, a philanthropically endowed academic computer
science institute within the campus of university of Chicago. Dr. Keshet's
research interests are in speech and language processing and machine
learning. His current research focuses on the design, analysis and
implementation of machine learning algorithms for the domain of speech and
language processing 
January 22 2012
11:1512:15 
Shai Avidan 

Coherency Sensitive Hashing
Coherency Sensitive Hashing (CSH) extends Locality Sensitivity Hashing
(LSH) and PatchMatch to quickly find matching patches between two
images. LSH relies on hashing, which maps similar patches to the same
bin, in order to find matching patches. PatchMatch, on the other hand,
relies on the observation that images are coherent, to propagate good
matches to their neighbors, in the image plane. It uses random patch
assignment to seed the initial matching. CSH relies on hashing to seed
the initial patch matching and on image coherence to propagate good
matches. In addition, hashing lets it propagate information between
patches with similar appearance (i.e., map to the same bin). This way,
information is propagated much faster because it can use similarity in
appearance space or neighborhood in the image plane. As a result, CSH
is at least three to four times faster than PatchMatch and more
accurate, especially in textured regions, where reconstruction
artifacts are most noticeable to the human eye. We verified CSH on a
new, large scale, data set of 133 image pairs.
joint work with Simon Korman 
March 4 2012
11:1512:15 
Amir Shpilka 

Polynomial Identity
In this talk, we consider the problem of estimating a potentially
sensitive (individually stigmatizing) statistic on a population. In
our model, individuals are concerned about their privacy, and
experience some cost as a function of their privacy loss.
Nevertheless, they would be willing to participate in the survey if
they were compensated for their privacy cost. These cost functions are
not publicly known, however, nor do we make Bayesian assumptions about
their form or distribution. Individuals are rational and will
misreport their costs for privacy if doing so is in their best
interest. Ghosh and Roth recently showed in this setting, when costs
for privacy loss may be correlated with private types, if individuals
value differential privacy, no individually rational direct revelation
mechanism can compute any nontrivial estimate of the population
statistic. In this paper, we circumvent this impossibility result by
proposing a modified notion of how individuals experience cost as a
function of their privacy loss, and by giving a mechanism which does
not operate by direct revelation. Instead, our mechanism has the
ability to randomly approach individuals from a population and offer
them a takeitorleaveit offer. This is intended to model the
abilities of a surveyor who may stand on a street corner and approach
passersby.
Joint work with Aaron Roth.
Manuscript available at http://arxiv.org/abs/1202.4741
bio: Katrina Ligett is an Assistant Professor of Computer Science and
Economics at Caltech. Prior to that, she was a postdoc at Cornell with
Bobby Kleinberg and Eva Tardos. She received her PhD from Carnegie
Mellon in 2009, advised by Avrim Blum. Her interests include
algorithmic game theory, online algorithms, learning theory, and data
privacy. 
March 11 2012
11:1512:15 
Yair Weiss 

Multidimensional Spectral
With the growing availability of very large datasets for machine learning, there has been
a surge of interest in methods based on ``semantic hashing'', i.e.
compact binary codes of datapoints so that the Hamming distance
between codewords correlates with similarity. We define the problem of finding binary codes that
reconstruct the {\em affinity} between datapoints, rather than their
distances. We show that this criterion is still intractable to solve
exactly, but a spectral relaxation gives an algorithm where the bits
correspond to thresholded eigenvectors of the affinity matrix, and as
the number of datapoints goes to infinity these eigenvectors converge
to eigenfunctions of LaplaceBeltrami operators, similar to the
recently proposed Spectral Hashing (SH) method. Unlike SH which uses
only single dimension eigenfunctions, our formulation requires
multidimensional eigenfunctions but we show how to use a
``kernel trick'' to allow us to compute with an exponentially large
number of bits but using only memory and computation that grows
linearly with dimension. Experiments shows that MDSH
outperforms the stateofthe art, especially in the challenging regime of small distances.
Joint work with Antonio Torralba (MIT) and Rob Fergus (NYU) 
March 18 2012
11:1512:15 
Katrina Ligett 

Take it or Leave it: Running a Survey when Privacy Comes at a Cost
In this talk, we consider the problem of estimating a potentially
sensitive (individually stigmatizing) statistic on a population. In
our model, individuals are concerned about their privacy, and
experience some cost as a function of their privacy loss.
Nevertheless, they would be willing to participate in the survey if
they were compensated for their privacy cost. These cost functions are
not publicly known, however, nor do we make Bayesian assumptions about
their form or distribution. Individuals are rational and will
misreport their costs for privacy if doing so is in their best
interest. Ghosh and Roth recently showed in this setting, when costs
for privacy loss may be correlated with private types, if individuals
value differential privacy, no individually rational direct revelation
mechanism can compute any nontrivial estimate of the population
statistic. In this paper, we circumvent this impossibility result by
proposing a modified notion of how individuals experience cost as a
function of their privacy loss, and by giving a mechanism which does
not operate by direct revelation. Instead, our mechanism has the
ability to randomly approach individuals from a population and offer
them a takeitorleaveit offer. This is intended to model the
abilities of a surveyor who may stand on a street corner and approach
passersby.
Joint work with Aaron Roth.
Manuscript available at http://arxiv.org/abs/1202.4741
bio: Katrina Ligett is an Assistant Professor of Computer Science and
Economics at Caltech. Prior to that, she was a postdoc at Cornell with
Bobby Kleinberg and Eva Tardos. She received her PhD from Carnegie
Mellon in 2009, advised by Avrim Blum. Her interests include
algorithmic game theory, online algorithms, learning theory, and data
privacy. 
March 25 2012
11:1512:15 
No talk (Open university Theory day) 
April 1 2012
11:1512:15 
Mike Fellows 

Parameterized and Multivariate Algorithmics: A Progress Report
The talk will survey the main ideas and motivations in parameterized complexity
and algorithmics (as for beginners) and then move on to a discussion of current frontiers. 
April 8 2012
11:1512:15 
No Talk: Pesach vacation 
April 15 2012
11:1512:15 
Kobi Nissim 

Privacy in Mechanism Design
I will discuss several issues on the seam between privacy and mechanism
design. In particular, I will present a recent construction of
approximately optimal mechanisms and show applications to the setting of
interdependent valuation, and to privacyaware mechanism design.

April 22 2012
11:1512:15 
Adi Avidor 

Building a Computing System for the World’s Information
We will review Google's approach for creating an infrastructure to its wide
number of products. We will present the architecture of the computing
platform and its holistic design. We then review Google's distributed
systems software infrastructure while elaborating on Google File System
(GFS) and the MapReduce framework.
Short Bio:
Adi Avidor works in Google for more than 5 years, from the opening
of the Tel Aviv office. He initiated and lead the engineering networking
group
in Google Israel. The group’s accomplishments were recognized in Q3’2008
as one of Google’s top 10 accomplishments for the quarter.
Adi holds a Ph.D (Uri Zwich, CS) in computer science as well as an M.Sc.
(Yossi Azar, CS) and a B.Sc. (Math & CS) all from Tel Aviv University. 
April 29 2012
11:1512:15 
Yehuda Lindel 

Making Secure Computation Practical
In this talk we will present the current state of the art of efficient
secure computation and its practicality. The talk will focus on different
approaches to making secure computation practical and the results of these
approaches. These approaches include issues of modelling and definitions,
construction paradigms for high efficiency, and the role of concrete
efficiency and implementations. 
May 6 2012
11:1512:15 
Yaron Lipman 

On Bounded Distortion Mapping Spaces of Triangular Meshes
Triangular meshes are prevalent in imaging sciences and numerical analysis.
Yet, basic tasks such as constructing bounded distortion and/or bijective
mappings of meshes are in many senses unsolved problems.
In this talk we will study the spaces of bounded distortion mesh mappings
and suggest a simple representation to these spaces. This representation
will motivate defining certain convex subsets that will be used to
construct algorithms that address some aspects of the mapping problems.
Yaron Lipman is a senior researcher in the Department of Computer Science
and Applied Mathematics at Weizmann Institute of Science. His research
interests are mainly in geometric processing and modeling, discrete
differential geometry, and approximation theory with applications. Yaron
received his B.Sc. in Computer Science and Mathematics, and a Ph.D.
in Applied Mathematics from TelAviv University, and was a
postdoctoral fellow in the Computer Science Department, and the Program in
Applied and Computational Mathematics at Princeton University. 
May 13 2012
11:1512:15 
Martin Kupiec 

Telomere length maintenance in yeast: Vertical and horizontal views
We are using the yeast sophisticated genetics and systems biology methodologies to dissect the mechanisms that maintain telomere length. Telomeres are the ends of the linear chromosomes, and play important roles in cancer and aging. 
May 20 2012
11:1512:15 
Ronen Feldman 

An Unsupervised Framework for Information Extraction
In the talk I will describe a framework for relation learning and
building of domainspecific relation extraction systems. I will
demonstrate several applications of the framework in the domains of
mining public medical forums and financial news and blogs. The case
studies demonstrate the ability of the system to achieve high accuracy
of relation identification and extraction with minimal human
supervision. I will also describe and demonstrate the performance of
VC's modifier learning mechanism and coreference resolution.
Bio:
Ronen Feldman is an Associate Professor of Information Systems at the
Business School of the Hebrew University in Jerusalem. He received his
B.Sc. in Math, Physics and Computer Science from the Hebrew University
and his Ph.D. in Computer Science from Cornell University in NY. He
was an Adjunct Professor at NYU Stern Business School. He is the
founder of ClearForest Corporation that was acquired by Reuters in 2007. He
has given more than 30 tutorials on text mining and information
extraction and authored numerous papers on these topics. He is the
author of the book "The Text Mining Handbook" published by Cambridge
University Press in 2007. 
May 27 2012
11:1512:15 
No Talk: Shavut 
June 3 2012
11:1512:15 
No Talk 
June 10 2012
11:1512:15 
Raphy Coifman 

Harmonic Analysis and inferential geometries of datasets
We will describe a synthetic overview of a range of ideas from
Mathematics and Machine learning, which address the transition from a
local similarity/differential model to a global configuration (analogous
to Newtonian Calculus).
In particular we describe the role of eigenvectors (of appropriate locally
learned ``differential'' transformations), as integration tools, and their
relation to multiscale hierarchical ontology building, a relation
generalizing the link between Fourier and Wavelet analysis, to the
context of clouds of points (data) in high dimensional Euclidean spaces.
We apply these ideas to organize and find hidden driving factors for
physical data, map out (in an automatic and purely data driven fashion),
databases of medical profiles, financial data and text documents. 
June 17 2012
11:1512:15 
Andrej Bogdanov 

Local cryptography  structure and security
Local cryptography studies cryptographic objects with a small number of
inputoutput dependencies, which allows for fast parallel implementations.
I will talk about structural properties of local oneway functions and
local pseudorandom generators, some conditions for their (in)security, as
well as bounds on the locality of randomness extraction procedures.
This talk is based on joint works with Youming Qiao, Alon Rosen, Benny
Applebaum, and Siyao Guo.


















CS Colloquium 20112012  Spring Semester: 

