Computer Science/Discrete Mathematics Seminar II

I will describe some recent results joint with V. Milman in which we take the computer science approach to derandomization and apply it in questions from asymptotic geometric analysis. The special type of questions requires an adaptation of the usual methods, which turns to be interesting in its own right. For example we prove a type of Bernstein inequality for certain random walks on expanders. We will review the history of the problems, the results, and give an essentially-full proof for one of the theorems.