TITLE: Gibbs Sampling, Orthogonal Polynomials, and Exponential Families

ABSTRACT: The Gibbs sampler (also known as the heat bath algorithm or Glauber dynamics) is a very widely used tool of scientific computing.
Useful analyses of the running time for anything like real examples lies mostly in the future. In joint work with Kshitij Kahare and Laurent Saloff-Coste, we have found classes of cases where sharp analyses can be carried out. The examples involve standard exponential families (binomial, Poisson, negative binomial, normal, gamma, hyperbolic). The associate operators can be explicitly diagonalized using "classical" orthogonal polynomials. The diagonalizations produce "new" identities and sharp analysis of the underlying chain. The chains arise in statistics, but include queuing and genetics examples.

Wojciech Szpankowski, Purdue University, USA.

TITLE: Algorithms, Combinatorics, and Information: Ubiquitous Trees

ABSTRACT: Algorithms are at the heart of virtually all computing technologies; combinatorics provides indispensable tools for finding patterns and structures arising in various problems of science and engineering; information permeates every corner of our lives and shapes our universe, so understanding and harnessing information allows the potential for significant advances. We discuss a handful of technical results of source coding (also known as data compression) to illustrate the interplay between algorithms, combinatorics, and information. We first present an algorithm that solves a long-standing problem of eliminating the devastating effect of a limited number of errors in the popular Lempel-Ziv'77 scheme. We achieve this goal by recovering multiple matches in LZ'77 and using them for error correction. An array of analytic, combinatorial, and probabilistic methods are applied to show that the number of redundant bits is well concentrated around the mean, a highly desirable property. Then, we deal with the method of types, a powerful technique in information theory, large deviations, and analysis of algorithms. We shall argue that counting types can be accomplished efficiently by enumerating Eulerian paths (Markov types) or binary trees with a given path length (universal types). This will lead us to the Knuth problem posed during the 2004 Analysis of Algorithms Seminar in Berkeley: what is the joint limiting distribution of the left and the right path lengths in a randomly selected binary tree built over n nodes? It turns out that the Knuth functional equation is very rich and covers such problems as the enumeration of binary trees, finding the limiting distribution of the total path length in such trees, enumeration of binary trees of a given path, the distribution of the area under a Bernoulli walk, and even the Kleitman-Winston conjecture. Finally, in the third part of the this talk, we design and analyze a one-to-one code whose average length is smaller than the source entropy in defiance of the lower bound of Shannon. We study the so called anti-redundancy and present a precise analysis. This relatively simple finding requires a combination of analytic tools such as precise evaluation of Bernoulli sums, the saddle point method, and theory of distribution of sequences modulo $1$.

BIO: Wojciech Szpankowski received his M.S. and Ph.D. degrees in Electrical and Computer Engineering from the Technical University of Gdansk in 1976 and 1980, respectively. Currently, he is Professor of Computer Science (and by courtesy Electrical and Computer Engineering) at Purdue University. In 1992 he was Professeur Invite at INRIA-Rocquencourt, France, in 1999 he was Visiting Professor at Stanford University, and in 2006 the Erskine Fellow at University of Canterbury, Christchurch, New Zealand. Szpankowski's research interests cover mainly analysis of algorithms and information theory, and also bioinformatics, analytic combinatorics, and stability problems of distributed systems. He published the book "Average Case Analysis of Algorithms on Sequences", John Wiley & Sons, 2001.Dr. Szpankowski has been a guest editor and an editor of technical journals, including the IEEE Transactions on Information Theory, Foundation and Trends in Communications and Information Theory, Theoretical Computer Science, the ACM Transaction on Algorithms, and Combinatorics, Probability, and Computing. He co-chaired the Information Theory and Networking Workshop, Metsovo, Greece, the "NSF Workshop on Information Theory and Computer Science Interface", Chicago, and the workshop "Information Beyond Shannon", Orlando. In June 2004 he directed the MSRI Graduate Program on the "Analysis of Algorithms and Information Theory". He is a Fellow of the IEEE.

Madhu Sudan, MIT, USA
TITLE: List-Decoding: A Survey
ABSTRACT: The theory of error-correction has had two divergent schools of thought, going back to the works of Shannon and Hamming.
In the Shannon school, error is presumed to have been effected probabilistically. In the Hamming school, the error is modeled as effected by an all-powerful adversary. The two schools lead to drastically different limits. In the Shannon model, a binary channel with error-rate close to, but less than, 50% is useable for effective communication. In the Hamming model, a binary channel with an error-rate of more than 25% prohibits unique recovery of the message.In this talk, we describe the notion of list-decoding, as a bridge between the Hamming and Shannon models. This model relaxes the notion of recovery to allow for a "list of candidates".
We describe some of the algorithmic results in this model, hopefully ending with the recent breakthroughs of Parvaresh and Vardy; and Guruswami and Rudra, that achieve optimal rate list-decodable codes over large alphabets.

BIO: Madhu Sudan received his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his Ph.D. from the University of California at Berkeley in 1992. From 1992-1997 he was a Research Staff Member at IBM's Thomas J. Watson Research Center. In 1997, he moved to MIT where he is now the Fujitsu Professor of Electrical Engineering and Computer Science.
He was a Fellow at the Radcliffe Institute for Advanced Study from 2003-2004, and a Guggenheim Fellow from 2005-2006.Madhu Sudan's research interests include computational complexity theory, algorithms and coding theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. He has served on numerous program committees for conferences in theoretical computer science, and was the program committee chair of the IEEE Conference on Computational Complexity '01, and the IEEE Symposium on Foundations of Computer Science '03. He is the chief editor of Foundations and Trends in Theoretical Computer Science, a new journal publishing surveys in the field. He is currently a member of the editorial boards of the Journal of the ACM and the SIAM Journal on Computing. Previously he served on the boards of the SIAM Journal on Discrete Mathematics, Information and Computation, and the IEEE Transactions on Information Theory.
Madhu Sudan is a recipient of numerous awards including the ACM Doctoral Dissertation Award (1992), the IEEE Information Theory Society Paper Award (2000), the Godel Prize (2001) and the Nevanlinna Prize (2002).

Lazslo Lovasz,Eotvos Lorand University, Budapest, Hungary.

TITLE: Algorithms on very large graphs
ABSTRACT: Very large graphs, like the internet or the human brain, represent new challenges to the graph theorist, both in understanding what notions are meaningful to define, what kind of algorithms can be studied, and how the efficiency if these algorithms should be understood. These graphs often change all the time, their structure is never seen as a whole, and their parameters are only approximately known.
One important step is to model these graphs, for example in the sense of giving algorithms that construct smaller graphs which have similar properties. In the case of dense graphs, Szemeredi's Regularity Lemma as well as more recent results on graph property testing provide such modeling tools. The theory of convergent graph sequences provides further modeling methods. In the case of sparse graphs, which are of greater practical interest, much less is known.
The talk surveys these results and discusses their algorithmic aspects.

BIO. Laszlo Lovasz was born in 1948 in Budapest, Hungary. He obtained his doctoral degree in mathematics from the Eotvos Lorand University, in Budapest, Hungary in 1971. He is a member of the Hungarian Academy of Sciences and several other Academies.
He taught mathematics and computer science at the University of Szeged, Eotvos Lorand University, Princeton University and Yale University. He was A.D.White Professor-at-Large at Cornell University,
and a Senior Researcher at Microsoft Research. Currently he is Director of the Institute of Mathematics at the Eotvos Lorand University in Budapest.
His awards include the George Polya Prize (1979), the Ray D.Fulkerson Prize (1982), the Brouwer Medal (1993), the Wolf Prize (1999), the Knuth Prize (1999) and the Godel Prize (2001). He is editor-in-chief of Combinatorica and editor of 12 other Journals.
His field of research is discrete mathematics, in particular its applications to the theory of algorithms and the theory of computing, and its interactions with classical mathematics. He wrote 4 research monographs and 4 textbooks, and over 250 research papers.