Abstract:
Expander graphs, over the last few decades, have played a pervasive role in almost all areas of theoretical computer science. Loosely, speaking an expander graph is an extremely well-connected graph despite being sparse. Recently, various high-dimensional analogues of these objects have been studied in mathematics and even more recently, there have been some surprising applications in computer science, especially in the area of property testing, coding theory and approximate counting. In this talk, I'll give a high-level introduction to these high-dimensional expanders (HDXs). In particular, we will view them through the perspective of random walks on graphs. Time permitting, we will then some see applications of these HDXs towards property testing, coding theory and matroid counting.
Bio:
Prahladh Harsha is an Associate Professor at the School of Technology and Computer Science at the Tata Institute of Fundamental Research (TIFR), Mumbai, India. He obtained his BTech degree in Computer Science and Engineering from IIT Madras in 1998 and his PhD in Computer Science from the Massachusetts Institute of Technology (MIT) in 2004. He has worked at Microsoft Research, TTI Chicago and has been at TIFR since 2010. Prahladh's research interests are in the area of theoretical computer science, with special emphasis on computational complexity theory. He is best known for his work in the area of probabilistically checkable proofs. Prahladh Harsha is a winner of the NASI Young Scientist Award for Mathematics and the Swarnajayanti Fellowship (Govt. of India). He is on the editorial board of the SIAM Journal of Computing and Algorithmica.
Faculty Host: Ruta Mehta
