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

Expanders are graphs that are both edge-sparse and well connected. They have been an instrumental tool in many results in mathematics and computer science, some of which seem to have little connection to graphs at all. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs — sparse and well connected hypergraphs.  HDXs have already played a key role in several recent results in theoretical computer science and combinatorics. However, much of their underlying theory remains unexplored.

Motivated by this, we will see what HDXs are, why they generalize expander graphs, and how they serve as a common setting for results in probability and computational complexity. 

I will illustrate their power by presenting new Chernoff-type inequalities for HDXs and explaining their applications to: 

1. Hardness amplification - constructing functions for which the best polynomial-time algorithm performs no better than random guessing.

2. Hardness of approximation - constructing natural problems for which even approximate solutions are intractable unless P=NP.

The talk will not assume prior background and is aimed at a broad audience. 

Bio: Yotam is a theoretical computer scientist working between combinatorics and computational complexity. His work studies combinatorial structures such as high-dimensional expanders, and their implications for algorithms and complexity theory. He is currently a postdoc fellow at the Institute for Advanced Study and received his PhD from the Weizmann Institute of Science.