Alex Lubotzky (Hebrew University of Jerusalem)

Expanders: From One-Dimensional to Multi-Dimensional

Lecture 1: Expander Graphs and Geometric/Topological Expanders
Date: Tuesday, November 18, 2014
Time: 5:15-6:15 pm
Location: Physics 204 
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
Date: Wednesday, November 19, 2014
Time: 4:00-5:00 pm
Location: Monroe 116 
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: Coboundry Expanders and Property Testing
Date: Thursday, November 20, 2014
Time: 4:00-5:00 pm
Location: Monroe 116 
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.