In which we prove properties of expander graphs.
CS359G Lecture 18: Properties of Expanders
3
In which we prove properties of expander graphs.
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