Alex Lubotzky

Einstein Institute of Mathematics and Weizmann Institute of Science

New directions in error correcting codes

Monday, April 17, 2023

6:00–7:00PM

008 Kemeny

Abstract: Error Correcting Codes (ECC) are used to detect and correct errors when data is transmitted from the sender to the receiver over a noisy channel. Shannon and Hamming laid the foundations of the mathematical theory of ECC over 75 years ago. Ever since then, it has been an intensive area of study in various branches of science. In the talk we will present some of the sources and highlights of this theory, putting an emphasis on the 1990s breakthrough of Sipser and Spielman, who created low-density parity check (LDPC) codes, as well as the recent solution to the long-standing problem of the existence of locally testable codes (LTC). These codes, whose existence was doubted for many years, enable the receiver to check if the message is mostly correct by reading only a few bits of it, a property that seems very counterintuitive!

High dimensional expanders: From Ramanujan graphs to Ramanujan complexes

Colloquium

Tuesday, April 18, 2023

3:15–4:15PM

041 Haldeman

Abstract: Ramanujan graphs are $k$-regular graphs with all nontrivial eigenvalues bounded (in absolute value) by $2\sqrt{k-1}$. They are optimal expanders (from a spectral point of view). Explicit constructions of such graphs were given in the 1980s as quotients of the Bruhat-Tits tree associated with $GL(2)$ over a local field $F$, by the action of suitable congruence subgroups of arithmetic groups. The spectral bound was proved using the work of Hecke, Deligne, and Drinfeld on the "Ramanujan conjecture" in the theory of automorphic forms. The work of Lafforgue, extending Drinfeld from $GL(2)$ to $GL(n)$, opened the door for the construction of Ramanujan complexes as quotients of the Bruhat-Tits buildings associated with $GL(n)$ over $F$. This way one gets finite simplicial complexes, which are simultaneously "random like'' and have strong symmetries. These seemingly contradictory properties make them very useful in applications to combinatorics and computer science, as well as in relation to Gromov's overlapping properties. We will survey some of these applications. All notions will be explained.

Group approximation, stability, and high dimensional expanders

Seminar talk

Wednesday, April 19, 2023

2:00PM–3:00PM

307 Kemeny

Abstract: Several well-known open questions, such as "are all groups sofic or hyperlinear?", have a common form: can all groups be approximated by asymptotic homomorphisms into the symmetric groups $Sym(n)$ (in the sofic case) or the unitary groups $U(n)$ (in the hyperlinear case)? In the case of $U(n)$, the question can be asked with respect to different metrics and norms. We answer, for the first time, some of these versions, showing that there exist finitely presented groups that are not approximated by $U(n)$ with respect to the Frobenius (or $L_2$) norm and many other norms. The strategy is via the notion of "stability," where some higher dimensional cohomology vanishing phenomenon is proven to imply stability. Using the Garland method (i.e., high dimensional expanders as quotients of Bruhat-Tits buildings), it is shown that some non-residually finite groups are stable and hence cannot be approximated. These groups are central extensions of lattices in $p$-adic Lie groups (constructed via a $p$-adic version of a result of Deligne). We will also discuss the connection between "stability" and "testability" from computer science. All notions will be explained with some suggestions for further research. Based on joint works with M. De Chiffre, L. Glebsky, A. Thom, I. Oppenheim, O. Becker and J. Mosheiff.