CS359G Lecture 18: Properties of Expanders

In which we prove properties of expander graphs.

CS254 Lecture 4 – The Polynomial Hierarchy

Today we show how to reduce the error probability of probabilistic algorithms, prove Adleman’s theorem that polynomial time probabilistic algorithms can be simulated by polynomial size circuits, and we give the definition of the polynomial hierarchy