^November December – 2009 ^January

Many applications call for estimating probabiities of rare, even previously unseen, events. We briefly describe the problem's theory, applications to classification and data compression, relation to works by Fisher, Shakespeare, Laplace, Good, Turing, Hardy, Ramanujan, and Shannon, and recent constructions of asymptotically optimal estimators. The talk is self contained and based on work with P. Santhanam, K. Viswanathan, J. Zhang, and others.

We will discuss complexity in worlds with a weak algebraic structure. We will start with a brief introduction to algebraic complexity, and explain Valiant's definitions of the algebraic analogs of P and NP. We will then explore these notions in weak algebraic structures which are not necessarily commutative or even associative. It turns out that even in such a world, permanent is NP-complete. We also consider hardness in these weak computational worlds: First, we show that the non-commutative complexity of permanent is related to the classical sum-of-squares problem. We also show that in a non-associative world, NP is strictly stronger than P. Joint work with Pavel Hrubes and Avi Wigderson.

The k-server problem is one of the most central and well studied problems in competitive analysis and is considered by many to be the "holy grail" problem in the field. In the k-server problem, there is a distance function d defined over an n-point metric space and k servers located at the points of the metric space. At each time step, an online algorithm is given a request at one of the points of the metric space, and it is served by moving a server to the requested point. The goal of an online algorithm is to minimize the total sum of the distances traveled by the servers so as to serve a given sequence of requests. The k-server problem captures many online scenarios, and in particular the widely studied paging problem. A twenty year old conjecture states that there exists a k-competitive online algorithm for any metric space. The randomized k-server conjecture states that there exists a randomized O(log k)-competitive algorithm for any metric space. While major progress was made in the past 20 years on the deterministic conjecture, only little is known about the randomized conjecture. We present a very promising primal-dual approach for the design and analysis of online algorithms. We survey recent progress towards settling the k-server conjecture achieved using this new framework.

In this talk I'll exhibit a simple method for analyzing dynamic data structures using various forbidden substructure theorems. The idea is to (1) transcribe the behavior of the data structure as some kind of combinatorial object, (2) show that the object does not contain some forbidden substructure, and (3) bound the size of any such object without this substructure. I'll show how to analyze path compression-based data structurses using forbidden 0/1 submatrices, then discuss some extremal problems on 0-1 matrices. This talk covers results from two papers to appear in SODA 2010.

Most 3D shapes are nowadays acquired using range scanning devices.Currently, scanners are capable of capturing complex shapes, large urban scenes and lately even motion. The initial representation of the shape consists of several properly transformed depth images, resulting in a point sampling of the surface. Typically, scan data consist of missing parts, noise in point coordinates and orientation, outliers and non-uniform sampled regions. Without prior assumptions and user interventions, the reconstruction problem is ill posed; an infinite number of surfaces pass through or near the data points. One of today's principal challenges is the development of robust point processing and reconstruction techniques that deal with the inherent inconsistencies in the acquired data set. In my talk I will present recent advances in geometric modeling, processing and reconstruction of point data. I will describe a deformable model for watertight manifold reconstruction. The model yields a correct topology interpretation of the reconstructed shape and allows topology control to a certain extent. Next, I will present a topology-aware interactive reconstruction technique. Topological ambiguities in the data are automatically detected and user interaction is used to consolidate topology reconstruction. Following, I will present a space-time technique for the reconstruction of moving and deforming objects. The motion of the object is described as an incompressible flow of matter which overcomes deficiencies in the acquired data such as persistent occlusions, errors and even entirely missing frames. Motivated by recent advancements in sparse signal reconstruction, I will present a "lower-than-L2" minimization scheme for sparse reconstruction. The sparsity principle gives rise to a novel global reconstruction paradigm for sharp point set surfaces which is robust to noise.

Two of most serious and fundamental problems Natural Language Processing are data sparsity and non-local reasoning. For example, let's consider the task of identifying people, locations and organizations in the following text (taken from Reuters): "BLINKER BAN LIFTED. Dutch forward Reggie Blinker had his indefinite suspension lifted by FIFA on Friday and was set to make his Sheffield Wednesday comeback on Saturday… Blinker missed his club's last two games after FIFA slapped a worldwide ban on him for appearing to sign contracts for both Wednesday and Udinese …" Many of the words, like 'Udinese' and 'Sheffield' are rare words that are unlikely to appear in the training data. On the other hand, the words 'Blinker' and 'Wednesday' in this text refer to a player and to a soccer team, and successfully identifying them as such requires global understanding of the text. In this talk I will discuss algorithms for reducing data sparsity and making non-local decisions in NLP. the running example will be the task of named entity recognition. Bio. Lev Ratinov received his BSc and MSc from BGU, now he's a Phd student in University of Illinois at Urbana-Champaign. He has published at ACL, AAAI, and gave a tutorial at EACL

Consider the setting of emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over the non-negative reals. Under this setting, weighted graph properties typically become random variables and we are interested in computing their statistical features. Unfortunately, this turns out to be computationally hard for some weighted graph properties albeit the problem of computing the properties per se in the traditional setting of algorithmic graph theory is tractable. For example, there are well known efficient algorithms that compute the emph{diameter} of a given weighted graph, yet, computing the emph{expected} diameter of a given randomly weighted graph is SharpP{}-hard even if the edge weights are identically distributed. In this work, we define a family of weighted graph properties and show that for each property in this family, the problem of computing the $k^{th}$ moment (and in particular, the expected value) of the corresponding random variable in a given randomly weighted graph $G$ admits a emph{fully polynomial time randomized approximation scheme (FPRAS)} for every fixed $k$. This family includes fundamental weighted graph properties such as the diameter of $G$, the emph{radius} of $G$ (with respect to any designated vertex) and the weight of a emph{minimum spanning tree} of $G$. Joint work with Amos Korman and Yuval Shavitt.

Phylogenetic trees represent evolutionary history, by showing the course of evolution from some extinct common ancestor to today's species. These trees can reveal connections between different species, teach us about extinct species, and help us understand the development of viruses, and other organisms with high mutation rate. The most common way of reconstructing phylogenetic trees is based on sequencing DNA from different species, and using similarities between sequences to infer the tree. This requires some model of how DNA evolves between an ancestor species and its descendants. The simplest model assumes that there are i.i.d mutations, and that each mutation is a substitution, and under this model, there are provably good reconstruction algorithm. However, recent studies show that insertions and deletions mutations are a serious cause of reconstruction errors, and can not be ignored. We present the first efficient algorithm for tree reconstruction when the mutations can be substitutions, insertions and deletions. The algorithm uses a clustering based approach, which builds small parts of the tree, and glues them together. In addition, the algorithm outputs a global alignment of the DNA sequences, which respects the evolutionary history. Based on joint works with Alex Andoni, Mark Braverman, Costis Daskalakis and Sebasiten Roch.