Mathematics Colloquium

A number of important problems in mathematics and theoretical computer science regard the ability to find a random-looking object in a fixed subset of the support of a random matrix. Such is the case for expander graphs, for example, where one asks how close various well-known bounds in random matrix theory can one get if one allows only the adjacency matrix of a graph. I will discuss the case when the bound of interest is one on the spectral norm of the matrix, and introduce an algebra of convolutions on polynomials that have been useful in attacking such problems. In particular, I will mention recent work regarding the existence of regular expander graphs of any size and any degree that is able to beat (for any fixed size) the asymptotically optimal bound provided by random matrix theory. I will also discuss a more recent result of Michael Cohen that shows one can actually construct such graphs in polynomial time. I also hope to mention some ongoing work in extending these ideas to biregular graphs.