Activities This Week

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.