Transactional data that occurs in telecommunications, financial, and retail applications can be represented as a graph. The size of such graphs can be very large so that mining such data poses significant technical challenges. We discuss our experience in mining large graphs paying special attention to the dynamic nature of the underlying applications, namely that the data presents itself not as a static data set but rather as a continuous data stream. We introduce a definition of a dynamic graph that has served us well in representing telecommunications data. We illustrate the ideas with examples from toll fraud detection.

Joint work with Corinna Cortes and Chris Volinsky.

Eigen-functions and spectrum of Schrödinger equation with potentials exhibiting random behavior were studied extensively in the last forty years starting from the famous works of Anderson and Harper. Properties of this type of equations are fundamental in understanding phase transitions in quantum mechanical disordered systems of solid state physics. The central part of this program consists of the study of the structure of the so-called set of resonances and intersections of the different shifts of this set under the translations in the space of potentials. The most important questions regarding the properties of the eigen-functions, in particular their exponential decay, known as Anderson localization, are closely related to this set. The answers to these questions are expected to depend on the dimension of the problem and also on the stochastic properties of the translations in the space of potentials (regular stationary processes, hyperbolic dynamical systems and just i.i.d. random values like in the Anderson model or quasi-periodic dynamics like in Harper’s model). These questions were studied first in perturbative regimes with use of ideas of KAM theory. In the last five years new methods of the analysis of resonances for quasi-periodic and skew-shifted dynamics were developed in the works of Bourgain, Goldstein and Schlag. In this talk we will describe the status of the main problems in this field, some recent results and prospective applications.

Finite-alphabet signals corrupted by discrete noisy channels arise naturally in a wide range of applications spanning fields such as statistics, engineering, and computer science. Examples include DNA sequence analysis and processing, text correction, Hidden Markov model state estimation, and image denoising. While the field of filtering or denoising of continuous-alphabet signals has a long history, the field of discrete denoising has seen far less progress.

In many discrete denoising applications, a good model for the randomness of the noisy channel is known, whereas the statistical description of the noiseless signal is either unknown or too complex. It is therefore of considerable interest to pose the problem of discrete universal denoising where no knowledge exists about the statistics of the noiseless signal while the channel statistics are assumed known.

I will present the DUDE algorithm for discrete universal denoising which has linear complexity and attains universal optimality in a stochastic sense as well as a stronger semi-stochastic sense.

I will also show several DUDE-based algorithms for channel decoding of systematically encoded redundant data.

Joint work with E. Ordentlich, G. Seroussi, M. Weinberger and T. Weissman.