דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

סיבות לעליונות של שיטות שחזור אקראיות על שיטות שחזור דטרמיניסטיות‫:‬ רובסטיות‫,‬ עקביות‫,‬ ואיכות ויזואלית
event speaker icon
גיא אוחיון (הרצאה סמינריונית למגיסטר)
event date icon
יום חמישי, 15.12.2022, 11:30
event location icon
הרצאת זום: 62049693728
Random walks on expanders are extremely useful in TOC. Unfortunately though, they have an inherent cost. E.g., the spectral expansion of a Ramanujan graph deteriorates exponentially with the length of the walk (when compared to a Ramanujan graph of the same degree). In this talk, we will see how this exponential cost can be reduced to linear by applying a permutation after each random step. These permutations are tailor-made to the graph at hand, requiring no randomness to generate. Our proof is established using the powerful framework of finite free probability and interlacing families that was introduced, around ten years ago, by Marcus, Spielman, and Srivastava in their seminal sequence of works on the existence of bipartite Ramanujan graphs of every size and every degree, and in their solution to the Kadison-Singer problem. Joint work with Gal Maor.