BIU theory seminar- June 21 : Roy Gotlib (BIU) - High Dimensional Expanders, Trickling Down and Random Walks
2 views
Skip to first unread message
Arnold Filtser
Jun 8, 2023, 2:01:09 AM6/8/23
to BIU Theory Seminar
Hello all,
Next week (Wed June 14) there will be no theory seminar.
In two weeks (Wed June 21, at 12) we will meet for our theory seminar.
Location: Building 605 room 14.
Speaker: Roy Gotlib (BIU)
Title: High Dimensional Expanders, Trickling Down and Random Walks
Abstract: High dimensional expanders are high dimensional analogues of expander graphs.
They play a key role in the construction of classic codes, quantum LDPC codes, agreement testing, sampling and more.
One key aspect of high dimensional expanders (that is not present in graph expanders) is that they exhibit local-to-global properties.
Another important property of high dimensional expanders is that random walks on their high dimensional edges converge rapidly.
In this talk I will present a new method that yields both the state of the art result in analysis of high dimensional random walks as well as Oppenheim's celebrated trickling down theorem.
Our result differs from previous results in the analysis of high dimensional random walks in that, while previous works examined the expansion in the viewpoint of the worst possible eigenvalue, our work relates the expansion of a distribution to its structure.
In sufficiently structured cases the result that I will present can be much better than the worst case while in the worst case it is equivalent to the previous state of the art result by Alev and Lau.
This is based on a result with Tali Kaufman.
In addition, I will briefly present the result of Anari et al. in which they show that the basis of a matroid can be sampled efficiently using the basis exchange walk.
I will not assume any familiarity with high dimensional expanders.
Title: High Dimensional Expanders, Trickling Down and Random Walks
Abstract: High dimensional expanders are high dimensional analogues of expander graphs.
They play a key role in the construction of classic codes, quantum LDPC codes, agreement testing, sampling and more.
One key aspect of high dimensional expanders (that is not present in graph expanders) is that they exhibit local-to-global properties.
Another important property of high dimensional expanders is that random walks on their high dimensional edges converge rapidly.
In this talk I will present a new method that yields both the state of the art result in analysis of high dimensional random walks as well as Oppenheim's celebrated trickling down theorem.
Our result differs from previous results in the analysis of high dimensional random walks in that, while previous works examined the expansion in the viewpoint of the worst possible eigenvalue, our work relates the expansion of a distribution to its structure.
In sufficiently structured cases the result that I will present can be much better than the worst case while in the worst case it is equivalent to the previous state of the art result by Alev and Lau.
This is based on a result with Tali Kaufman.
In addition, I will briefly present the result of Anari et al. in which they show that the basis of a matroid can be sampled efficiently using the basis exchange walk.
I will not assume any familiarity with high dimensional expanders.
Arnold Filtser
Jun 19, 2023, 3:12:33 AM6/19/23
to BIU Theory Seminar
Reminder - this Wednesday (in two days) we will meet for our theory seminar.
Best,
Arnold
Reply all
Reply to author
Forward
0 new messages