Georgia Institute of Technology College of Sciences

Random matrices arise naturally in various contexts ranging from theoretical physics to computer science. In a large part of these problems, it is important to know the behavior of the spectral characteristics of a random matrix of a large but fixed size. We will discuss a recent progress in this area illustrating it by problems coming from combinatorics and computer science: Condition number of “full” and sparse random matrices. Consider a system of linear equations Ax = b where the right hand side is known only approximately. In the process of solving this system, the error in vector b gets magnified by the condition number of the matrix A. A conjecture of von Neumann that with high probability, the condition number of an n × n random matrix with independent entries is O(n) has been proven several years ago. We will discuss this result as well as the possibility of its extension to sparse matrices. Random matrices in combinatorics. A perfect matching in a graph with an even number of vertices is a pairing of vertices connected by edges of the graph. Evaluating or even estimating the number of perfect matchings in a given graph deterministically may be computationally expensive. We will discuss an application of the random matrix theory to estimating the number of perfect matchings in a de- terministic graph. Random matrices and traffic jams. Adding another highway to an existing highway system may lead to worse traffic jams. This phenomenon known as Braess’ paradox is still lacking a rigorous mathematical explanation. It was recently explained for a toy model, and the explanation is based on the properties of the eigenvectors of random matrices.

Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc? We will survey both classical and recent results on the problem, emphasizing both algorithmic and complexity aspects. Some elegant hardness results will make an appearance in dimension as small as three. If time permits, we will discuss connections to Presburger Arithmetic and decidability problems for irrational polyhedra. Joint work with Danny Nguyen.

The colloquium will be the second lecture of the TRIAD Distinguished Lecture Series by Prof. Sara van de Geer. For further information please see http://math.gatech.edu/events/triad-distinguished-lecture-series-sara-van-de-geer-0.

This talk is about the structure theory of measure-preserving systems: transformations of a finite measure space that preserve the measure. Many important examples arise from stationary processes in probability, and simplest among these are the i.i.d. processes. In ergodic theory, i.i.d. processes are called Bernoulli shifts. Some of the main results of ergodic theory concern an invariant of systems called their entropy, which turns out to be intimately related to the existence of `structure preserving' maps from a general system to Bernoulli shifts. I will give an overview of this area and its history, ending with a recent advance in this direction. A measure-preserving system has the weak Pinsker property if it can be split, in a natural sense, into a direct product of a Bernoulli shift and a system of arbitrarily low entropy. The recent result is that all ergodic measure-preserving systems have this property. This talk will assume graduate-level real analysis and measure theory, and familiarity with the basic language of random variables. Past exposure to entropy, measure-theoretic probability or ergodic theory will be helpful, but not essential.