Activities This Week

Actions of countable discrete groups $\Gamma$ on a compact (metrizable) group $X$ by (continuous) group automorphisms are a rich class of dynamical systems. The case where $X$ is abelian is an important subclass, also called “algeraic actions”. By Pontryagin duality, algebraic actions are in one-to-one correspondence with $\mathbb{Z}\Gamma$-modules. There is a fascinating “dictionary” between the two, a beautiful interplay between dynamics, Fourier analysis, and commutative or noncommutative algebra. In the last several years, much progress has been made towards understanding the algebraic actions of general countable groups. Somehow surprisingly, operator algebras turn out to be important for such a study. This introductory talk will cover some basic aspects of the theory. (New results and open questions might be discussed in a followup talk).

Expander graphs have many wonderful properties: They are highly connected, pseudorandom, and random walks on expanders are rapidly mixing. The study of these objects has been immensely useful and fruitful for both applicative and theoretical fields. Recently, there has been a lot of interest in the study of generalizations of expander graphs to d-uniform hypergraphs. Several competing definitions have been proposed, each corresponding to a different property of expander graphs. Understanding these definitions, their applications, and the relations between them is the goal of this emerging field.

In a joint work with Alexander Lubotzky and Ron Rosenthal, we proved the existence of bounded degree coboundary expanders, a concept that generalizes high connectivity in graphs. Our work makes use of Peter Keevash’s recent construction of designs: We show that the union of a constant number of designs constructed according to Keevash’s random construction is with high probability a good coboundary expander.

The expander mixing lemma quantifies the extent to which an expander graph is pseudorandom. In a joint work with Nati Linial, we asked if there exist pseudorandom designs. In particular, we conjectured that a typical Latin square design is pseudorandom. This has implications for the Algebraic concept of quasirandom groups, introduced by Gowers. Our conjecture implies that there exist maximally quasirandom quasigroups, and we prove this fact.

There remain many promising directions for further research.

בתחום של אופטימיזציה קמורה, הרבה בעיות פרקטיות ניתן למדל כבעיות הכלה בין קבוצות קמורות שמוגדרות ע”י אי-שיוויון לינארי מטריציאלי. זהו תחום חדש יחסית, אך ישנם שימושים וקשרים רבים לתורת האינפורמציה הקוונטית, גיאומטריה אלגברית ממשית, ותורת המטריצות.

באופן כללי, לבדיקת ההכלה בין קבוצות קמורות כאלו יכולה להיות סיבוכיות גבוהה (NP-Hard). לעומת זאת, מסתבר שאפשר “להחליש” את הבעיה לבעיית הכלה בין קבוצות קמורות מטריציאלית, כך שבדיקת ההכלה נעשית כמעט בזמן ריצה פולינומיאלי.

בהרצאה נסקור בעיקר היבטים תיאורטים וגיאומטרים של הבעיות הללו. נסביר איך לעבור מהבעיה המקורית לבעיה הנוחה יותר, ואת הקשרים והשימושים לתורת האינפורמציה הקוונטית. במידה והזמן יאפשר, נסביר איך לכמת את השגיאה שבמעבר בין הבעיות, וכיצד סימטריה של גופים קמורים במרחב מאפשרת להעריך את השגיאה הזאת. הרקע הנדרש להרצאה הוא קורס באלגברה 2.