Course 1: New trends in expanders based on the method of interlacing polynomials
Instructor: Doron Puder
Lecture 1: Interlacing Polynomials and Ramanujan Graphs of all DegreesRamanujan graphs are optimal expander graphs. In 2013, Marcus, Spielman and Srivastava solved a long standing open problem and proved the existence of bipartite Ramanujan graphs of all degrees. The main new tool they use is the method of interlacing polynomials. We will introduce their work, and through it, the method of interlacing polynomials. If time permits, we will also point to a connection with the approximation of a matrix permanent.
Lecture 2: Interlacing Polynomials and the proof of the Kadison-Singer ProblemThe initial motivation of Marcus, Spielman and Srivastava in developing the method of interlacing polynomials was in their study of the Kadison-Singer Problem. We will describe their solution to this problem, which is probably the most impressive usage to date of this method.
Lecture 3: Introduction to the Theory of Group RepresentationsThe theory of group representations is a central area in Mathematics since the beginning of the 20th century. It also has a growing set of applications in computer science. We will give a brief introduction to the theory. Our focus will be on representations of the Symmetric Group.
Lecture 4: Card Shuffling and expandersHow long does it take to reach a near perfect random deck of cards if we shuffle the deck by taking two cards at random and swap them? In a beautiful application to Representation Theory, Diaconis and Shahshahani show that O (n log n) swaps lead to a nearly perfect random deck. This manifests a common theme: representation theory can be used to prove certain graphs (mostly Cayley graphs) are expanding.