Randomness Reduction in Some Results of Asympotic Geometric Analysis

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Randomness Reduction in Some Results of Asympotic Geometric Analysis
Speaker:Shiri Artstein
Affiliation:IAS
Date:Tuesday, May 16
Time/Room:10:30am - 12:30pm/Dilworth Room

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.