^April May – 2011 ^June

The ability to share and reconcile similar data on remote hosts with minimum communication is fundamental and inherent to a wide variety of networking applications, ranging from maintenance of your contacts across smartphones to synchronizing video fragments from moon rovers. In this talk we provide a selective survey of ten years of our research on this problem, together with applications to the information theory and cryptography communities.

We will begin with a concrete formalization of the problem of reconciling sets, and our initial solution based on polynomial interpolation. We will then present and analyze information-theoretic bounds, estimation techniques, and interactive solutions to this problem, together with an extension to string reconciliation. Throughout, we will describe applications tied to this problem and developed by others, such as the current standard for synchronizing PGP key databases and secure sketches for biometric authentication.

A coreset (or, core-set) for a given problem is a "compressed" representation of its input, in the sense that a solution for the problem with the (small) coreset as input would yield an approximate solution to the problem with the original (large) input. Using traditional techniques, a coreset usually implies provable linear time algorithms for the corresponding optimization problem, which can be computed in parallel, via one pass over the data, and using only polylogarithmic space (i.e, in the streaming model). During the recent years, coresets were suggested for problems such as k-means clustering, classification, facility location, linear regression, PCA, and matrix approximation. I will give an introduction to this new paradigm, including recent implementation in the context of computer vision. Based on a paper with Michael Langberg (STOC'11), and a paper Nir Sochen and Micha Feigin (SSVM'11)

This talk describes a body of work aiming for a paradigm shift in automatic multiview reconstruction and calibration. The new paradigm correlates the differential geometry of image curves and surfaces in contrast to using isolated image features such as SIFT/HOG. The current multiview geometry techniques have been developed based on the ideas from Projective Geometry and generally use isolated feature points in conjunction with RANSAC and Bundler, and result in unorganized cloud of point reconstructions. Our approach is complementary and uses the differential geometry attributes of curves and surfaces as the basic signature to correlate across views for both calibration and reconstruction. We discuss two specific efforts. First, we show that curve fragments can be correlated in multiple views and reconstructed to form a 3D Curve Sketch, an initial scaffold onto which surface patches will be reconstructed. Second, we show that the differential geometry attribute of curves can be used in registration of 3D models to 2D images. The results of other projects underway are also highlighted.

We explore dynamic environments in which computational nodes, or decision makers, follow simple and unsophisticated rules of behavior (e.g., repeatedly "best replying" to others' actions, and minimizing "regret") that have been extensively studied in game theory and economics. Our aim is to understand when convergence of the resulting dynamics to an equilibrium point is guaranteed even if nodes' interaction is not synchronized (e.g., as in Internet protocols and large-scale markets). We exhibit general positive and negative results and consider their implications across a wide variety of interesting and timely applications: routing, congestion control, game theory, social networks and circuit design. We also investigate incentives in our framework. Joint work with Aaron D. Jaggard and Rebecca N. Wright (2011) Noam Nisan, Gregory Valiant and Aviv Zohar (2011) Alex Fabrikant (in progress).

TBA

I discuss the syntactic-parsig problem: the automatic assignment of syntactic structure to sentences in natural language text, with a focus on parsing Hebrew, a language with rich morphology. Syntactic-parsing is an instance of a structured-prediction, a subfield of machine-learning concerned with learning to map complex inputs (like sentences) to complex outputs (like trees). I present the common framework for structured prediction, based on problem-decomposition and dynamic-programming, and show some cases in natural language where independence assumptions of that framework fail. I then present Easy-First parsing, a novel algorithm for syntactic parsing which is based on a different set of assumptions, and which makes it easy to incorporate a much richer feature sets than the dynamic-programming approach. The algorithm works by modeling the set of decisions made by constructing the output structure instead of directly modeling the structure itself. As a consequence, at each step the algorithm can observe partial structures and exploit rich contextual information to guide further decisions. The algorithm works in a greedy fashion by delegating the search to the training phase, making it particularly fast at inference time. I present results of experiments on Hebrew data sets indicating a parsing accuracy of up to 81.5%, a substantial improvement over other approaches. The method also works well for English, leading to state-of-the-art parsing results.

Structured prediction techniques have applications in other domains, I briefly report on application to computational biology (RNA structured prediction) where we also reach state-of-the-art results (joint work with Shay Zakov and Michal Ziv-Ukelson).

Symmetry breaking is an important task for distributed systems. Well-known problems involving symmetry breaking are the coloring and maximal independent set problems. They lie at the heart of many scheduling problems such as computing a TDMA schedule in wireless networks or for scheduling transactions in a multi-core system. In this talk, I consider both problems and look at different graph classes. A few randomized and deterministic algorithms will be presented in the message passing model.

Galperin and Wigderson proposed a succinct representation for graphs, that uses number of bits that is logarithmic in the number of nodes. They proved complexity results for various decision problems on graph properties, when the graph is given in a succinct representation. Later, Papadimitriou and Yannakakis showed, that under the same succinct encoding method, certain class of decision problems on graph properties becomes exponentially hard. We consider the complexity of the Permanent problem when the graph/matrix is given in a restrict succinct representation. We present an optical architecture that is based on the holographic concept for solving balanced inputs of the Succinct Permanent problem.

The talk will include both a theoretical results (relating establishing a computational complexity of some problems) and an optical implementation of the proposed algorithm.

Demanding historical data analysis like forecasting, formerly dependent on specialized data warehouses and temporal databases, can become available to everyday applications in off-the-shelf data stores. The challenge is to organize historical states so that they are ``always there'' when needed and "not in the way" when not. Retro approach integrates a low-level long-lived consistent snapshot system into a data store, allowing to run historical data analysis programs against the snapshots, side by side with programs running against the current state. The approach is attractive for several reasons. Applications can take snapshots at any frequency without disrupting the data store, and can garbage collect unneeded snapshots at low cost, an important feature in a long-lived system. Analysis programs can access snapshots at a cost that is independent of update workload and history length even for very old snapshots. A principled methodology allows to construct the snapshot system protocols in a modular way from the data store protocols, allowing to implement the snapshot system without extensive modifications to the data store internals, making the approach suitable in off-the-shelf data stores. The talk will describe the new techniques that underly Retro and present preliminary performance results from a prototype we built in Berkeley DB, indicating Retro is efficient, imposing moderate performance penalty on the native data store, on expected common workloads.

Bio: Liuba Shrira is a Professor in the Computer Science Department at Brandeis University, and is affiliated with the Computer Science and Artificial Intelligence Laboratory at MIT. She has been affiliated with Microsoft Research, Cambridge, UK, Microsoft Research Asia, Beijing, and is currently visiting the Computer Science Department, in the Technion, Haifa. Her research interests span aspects of design and implementation of distributed systems and especially storage systems. This includes fault-tolerance, availability and performance issues. Her recent focus is on long-lived transactional storage, time travel (in storage), software upgrades, and support for collaborative access to long-lived objects.