^May June – 2004

Google's PageRank algorithm for web search involves computing the principal eigenvector of a stochastic matrix describing the hyperlink structure of the World Wide Web. Since the web is a highly dynamic structure, with new pages constantly being added or removed, the update problem is an important problem in web search. We address the problem of efficiently recomputing the principal eigenvector of the web hyperlink matrix after small perturbations in the link structure of the web.

We present an algorithm that is motivated by the empirical observation that the convergence patterns of web pages in the PageRank algorithm have a nonuniform distribution. Specifically, many pages converge to their true PageRank quickly, while relatively few pages take a much longer time to converge. This algorithm, called Adaptive PageRank, avoids redundant computations associated with the PageRanks of pages that have already converged.

We show empirically that Adaptive PageRank speeds up the computation of PageRank even in the standard case, and that is is much more effective in the context of updates.

Coding theory addresses the design and analysis of codes that enable communication over noisy channels. Two types of channels that have been extensively considered are the "binary symmetric" channel and the "adversarial" channel. In a binary symmetric channel each bit of the sent message is flipped independently with some probability p, implying that the noise imposed by the channel is "random" in nature where the "amount" of noise is determined by p. In an adversarial channel the message is treated as a whole, and the noise may be an arbitrary (and malicious) function of the message being sent, as long as it does not effect more that a certain fraction (say p) of the bits transmitted.

Roughly speaking, any code designed for an adversarial channel can be used on a corresponding binary symmetric channel successfully, whereas the contrary is not necessarily true. In this work we will present a construction which transforms the "best" codes for binary symmetric channels into codes for corresponding adversarial channels.

Of course there is a catch: the "codes" we present assume that the sender and the receiver of the message have a joint secret random string (which is not known to the channel). These codes are referred to as "private" codes (also known as "random codes", i.e. a distribution over codes as apposed to a single code). Intuitively, this private randomness allows a reduction between the random and adversarial channels. Such a reduction is simple once the size of the joint random string is larger than $n\log{n}$ [here the codes are a subset of ${0,1}^n$].

In this work we present private codes in which this size is $O[\log{n}]$. Moreover, we show that our result is tight. Namely, to design private codes that allow communication over adversarial channels which meet the bounds achievable when communicating over binary symmetric channels, an amount of $\Omega[\log{n}]$ shared random bits are required. To the best of our knowledge, no prior results of this nature have been presented in the past. As part of our proof we establish a connection between list decodable codes and private codes which complements a recent result of Guruswami [CCC '03] on list decoding with side information.

The PseudoPolar FFT (PPFT) is a fast and accurate numerical algorithm for the computation of the 2D and 3D Fourier transform on a non Cartesian grid, which resembles the polar grid. In this talk we demonstrate its applicability to several fundamental problems in computer vision. We start by presenting the Angular Difference

Function (ADF) as a measure for the analysis of rotational properties of images and demonstrate its applicability to rotation estimation and symmetry detection in two and three dimensions. Contrary to other Fourier based schemes, the proposed algorithms do not use any interpolation. Thus, they are significantly faster, more accurate and can be shown to be algebraically accurate.

Finally we discuss on going work on temporal motion analysis and directional filters using the PPFT

Joint work with Amir Averbuch, Yoel Shkolnisky and Nisim Peled

We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p (resp., r{p }. We give algorithms that reconstruct the clusters from the graph with high probability. Compared to previous studies, our algorithms have lower time complexity and apply under wider parameter range.

Finite metric spaces and their (Lipschitz) embeddings have proved to be powerful algorithmic tools in recent years. Such techinques are used in combinatorial approximation, online computation, learning, data-minning, and bioinformatics. In this talk, I will describe some recent results on metric embeddings, including Ramsey-type problems, Multi embedding, embedding of low-dimensional metrics and applications for the online metrical task system problem.

D. Braha and Y. Bar-Yam. Physical Review E. Vo. 69 (1). 2004.

The last few years have led to a series of discoveries that uncovered statistical properties that are common to a variety of diverse real-world social, information, biological and technological networks. The goal of the present paper is to investigate the statistical properties of several man-made networks (including software, Internet) and discuss their significance. We show that these networks have properties that are like those displayed by information, biological and technological networks. The talk assumes no prior knowledge of complex networks theory, and will be of interest to the general public as well as to the specialist.