Alex Lubotzky - Virginia Mathematics Lectures - November 18-20, 2014

Event start date: Tuesday, November 18, 2014

Virginia Mathematics Lectures »
Alex Lubotzky Poster

Alex Lubotzky (Hebrew University of Jerusalem)
Expanders: From One-Dimensional to Multi-Dimensional
  • Lecture 1: Expander Graphs and Geometric/Topological Expanders
  • Lecture 2: From Ramanujan Graphs to Ramanujan Complexes
  • Lecture 3: Coboundary Expanders and Property Testing

Lecture 1: Expander Graphs and Geometric/Topological Expanders

Abstract: Expander graphs have played an important role, in the last four decades, in many areas of computer science. Recently they have already found applications in pure mathematics. We describe some of this history and present in these three talks some recent efforts to build a high-dimensional theory of expanders. We will start with Gromov’s geometric and topological expanders.

Lecture 2: From Ramanujan Graphs to Ramanujan Complexes

Abstract: Ramanujan graphs are optimal expanders. Their explicit construction is based on deep results of Deligne and Drinfeld in the theory of automorphic forms of \(GL(2)\). The work of Lafforgue for \(GL(d)\) enables the developments of high-dimensional objects: the Ramanujan complexes. These simplical complexes/hyper graphs enjoy some remarkable properties, being random-like but at the same time very symmetric. We will show how this helps to solve some problems in computer science (e.g., error-correcting codes) and in geometry.

Lecture 3: Coboundary Expanders and Property Testing

Abstract: Another direction of generalizing expanders from graphs to simplical complexes was proposed independently by Linial-Meshulam (in the context of developing Erodos-type theory of random simplical complexes) and by Gromov (when studying overlapping properties). We explain this notion and show a surprising connection with “property testing” which is a subject of fundamental importance, in theory and practice, in computer science.

Last updated: Monday, October 6, 2014