Georgia Institute of Technology College of Sciences

Research Horizons features Lunch Fun Break! The purpose is to create an opportunity for all graduate students, new and experienced, domestic and international, to meet, eat and have fun.AGENDA: ***"Suggestion box" for graduate students will be displayed in Faculty Lounge Skiles 236.*** Propective students' visit on Friday, April 2. *** Game: "Can you comunicate in silience?" *** PIZZAs, soft DRINKs, relax and have fun. ***

The Scenery Reconstruction Problem consists in trying to reconstruct a coloring of the integers given only the observations made by a random walk. For this we consider a random walk S and a coloring of the integers X. At time $t$ we observe the color $X(S(t))$. The coloring is i.i.d. and we show that given only the sequence of colors $$X(S(0)),X(S(1)),X(S(2)),...$$ it is possible to reconstruct $X$ up to translation and reflection. The solution depends on the property of the random walk and the distribution of the coloring. Longest Common Subsequences (LCS) are widely used in genetics. If we consider two sequences X and Y, then a common subsequence of X and Y is a string which is a subsequence of X and of Y at the same time. A Longest Common Subsequence of X and Y is a common subsequence of X and Y of maximum length. The problem of the asymptotic order of the flucutation for the LCS of independent random strings has been open for decades. We have now been able to make progress on this problem for several important cases. We will also show the connection to the Scenery Reconstruction Problem.

Sampling from and approximately counting the size of a large set of combinatorial structures has contributed to a renaissance in research in finite Markov chains in the last two decades. Applications are wide-ranging from sophisticated card shuffles, deciphering simple substitution ciphers (of prison inmates in the California state prison), estimating the volume of a high-dimensional convex body, and to understanding the speed of Gibbs sampling heuristics in statistical physics. More recent applications include rigorous estimates on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the discrete logarithm problem in finite cyclic groups. The lecture will be a brief (mostly self-contained) introduction to the Markov Chain Monte Carlo (MCMC) methodology and applications, and will include some open problems.

Olof Sisask and myself have produced a new probabilistic technique for finding `almost periods' of convolutions of subsets of finite groups. In this talk I will explain how this has allowed us to give (just recently) new bounds on the length of the longest arithmetic progression in a sumset A+A.