^April May – 2012 ^June

In this talk we consider weak and strong games played on the edge set of the complete graph $K_n$. Given a graph $G=(V,E)$ and a graph property P, in the weak game $P$ two players, called Maker and Breaker, alternately claim edges from $E$. Maker wins the game as soon as the graph spanned by his edges possesses the property P. If by the time all the edges have been claimed Maker does not win, then the game ends in a draw. In the strong game $P$ two players, called Red and Blue, alternately claim edges from $E$. The winner is the FIRST player whose graph possesses $P$. We consider the $k$-vertex-connectivity game, played on the edge set of $K_n$. We first study the weak version of this game and prove that, for any positive integer $k$ and sufficiently large $n$, Maker has a strategy for winning this game within $lfloor k n/2 rfloor + 1$ moves which is clearly best possible. This answers a question of Hefetz, Krivelevich, Stojakovich and Szabo. We then consider the strong $k$-vertex-connectivity game. For every positive integer $k$ and sufficiently large $n$, we describe an explicit first player's winning strategy for this game. this is a joint work with Dan Hefetz.

The disagreement coefficient of Hanneke has become a central data independent invariant in proving active learning rates. It has been shown in various ways that a concept class with low complexity together with a bound on the disagreement coefficient at an optimal solution allows active learning rates that are superior to passive learning ones. We present a different tool for pool based active learning which follows from the existence of a certain uniform version of low disagreement coefficient, but is not equivalent to it. In fact, we present two fundamental active learning problems of significant interest for which our approach allows nontrivial active learning bounds. However, any general purpose method relying on the disagreement coefficient bounds only fails to guarantee any useful bounds for these problems. The tool we use is based on the learner's ability to compute an estimator of the difference between the loss of any hypotheses and some fixed "pivotal" hypothesis to within an absolute error of at most $eps$ times the $ell_1$ distance (the disagreement measure) between the two hypotheses. We prove that such an estimator implies the existence of a learning algorithm which, at each iteration, reduces its excess risk to within a constant factor. Each iteration replaces the current pivotal hypothesis with the minimizer of the estimated loss difference function with respect to the previous pivotal hypothesis. The label complexity essentially becomes that of computing this estimator. The two applications of interest are: learning to rank from pairwise preferences, and clustering with side information (a.k.a. semi-supervised clustering). They are both fundamental, and have started receiving more attention from active learning theoreticians and practitioners. Joint work with Ron Begleiter and Esther Ezra

In 1934 H. Whitney posed the following problem: Let $f$ be a function defined on a closed subset $E$ of $R^n$. How can we tell whether $f$ extends to a $C^m$-smooth function defined on all of $R^n$? We discuss different aspects of this classical problem including its interesting connections with Convex Geometry (Helly's theorem), Lipschitz selections of set-valued functions and Analysis on Riemannian manifolds. The main part of the talk will be addressed to the "finiteness principal" which states that the Whitney extension problem can be reduced to the same kind of the problem, but for finite sets with prescribed numbers of points. We will present several constructive criteria for restrictions of $C^2$-functions and Sobolev $W^1_p$ and $W^2_p$-functions to arbitrary closed subsets of $R^2$.

The k-server problem is one of the most fundamental and extensively studied problems in online computation. Suppose there is an n-point metric space and k servers are located at some of 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 this request is served by moving a server to the requested point (if there is no server there already). The cost of serving a request is defined to be the distance traveled by the server. Given a sequence of requests, the task is to devise an online strategy minimizing the sum of the costs of serving the requests. We give the first polylogarithmic-competitive randomized online algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of O(log^3 n log^2 k) for any metric space on n points. Our algorithm improves upon the deterministic (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou whenever n is sub-exponential in k. Joint with Nikhil Bansal, Aleksander Madry and Seffi Naor

We present a novel framework for the query-performance prediction task. That is, estimating the effectiveness of a search performed by a search engine in response to a query in lack of relevance judgments. The framework is based on estimating the utility that a given document ranking provides with respect to an information need expressed by the query. To address the uncertainty in inferring the information need, we estimate the utility by the expected similarity between the given ranking and those induced by relevance language models. Specific query-performance predictors instantiated from the framework are shown to substantially outperform state-of-the-art predictors. In addition, we present an extension of the framework that results in a unified prediction model that can be used to derive and/or explain several previously proposed post-retrieval predictors which are presumably based on different principles.

Monitoring, interpretation, and analysis of large amounts of time-stamped data are tasks that are at the core of tasks such as the management of chronic patients, the detection of malware, or the integration of Intelligence data from multiple sources, and the related task of learning new knowledge from the accumulating data. In the case of the medical domain, these tasks are crucial for chronic-patient care, retrospective quality assessment, and clinical research. I will briefly describe several conceptual and computational architectures developed over the past 20 years, mostly by my research teams at Stanford and Ben Gurion universities, for knowledge-based performance of these tasks, and will highlight the complex and interesting relationships amongst them. Examples of such architectures include the IDAN and Momentum goal-directed and data-driven temporal-abstraction architectures, the KNAVE-II and VISITORS interactive-exploration frameworks for single and multiple longitudinal records, and the KarmaLego temporal data mining methodology. I will also point out the progression from individual-subject monitoring and therapy, to multiple-patient aggregate analysis and research, and finally to the learning of new knowledge. This progression, however, can also be viewed as a positive-feedback loop, in which new knowledge is brought back to bear upon both individual-patient management as well as on the learning of new and meaningful (temporal) associations.

In many real-world problems, a big scale gap can be observed between micro- and macroscopic scales of the problem because of the difference in mathematical (engineering, social, biological, physical, etc.) models and/or laws at different scales. The main objective of the multiscale algorithms is to create hierarchies of coarse problems, each representing the original problem at different scales with fewer degrees of freedom. We will discuss different strategies of creating these hierarchies and other components of multiscale methods for several large-scale applications: linear ordering for mapping problems in HPC, response to infection spread and cyber attacks, network compression, graph partitioning/clustering, etc.