All talks will be given by Irit Dinur (Weizmann)

09:00-09:50 Expansion & hardness of approximation
10:00-10:50 Low degree agreement test and unique games
14:00-14:50 (joint w CS colloquium)  "Unique games is 1/2-hard"
15:00-15:50 On the Grassmann complex

Abstracts:
Part I (9:00-11:00) 
9:00-10:00
I will describe expansion as a decoding procedure, using as an example the (familiar) coboundary expansion of the complete complex. I will then explain how this relates to hardness of approximation results, and describe the 1% vs the 99% regimes.

10:00-11:00
I will describe a theorem of Raz-Safra (1997) on the "plane-vs-plane agreement test".
From here we will build up to the definition of unique games. 

Part II (14:00-16:00)
14:00-15:00
The unique games conjecture ​stands at the center of the area of hardness of approximation. If true it implies a beautiful landscape featuring a single explanation for the complexity of an entire class of approximation problems. If false, it would mean new algorithms have been discovered. I will give some background on the area, and describe recent progress towards a proof of the unique games conjecture.

15:00-16:00
A central  ingredient in the proof of 1/2-hardness for UG is the Grassmann complex. 
​Although not a simplicial complex​, it​ ​is still interesting to view it as a complex.