Chennai Mathematical Institute


M.Sc Thesis Talk
2.00 p.m., Lecture Hall 2
Explicit, Almost Optimal Epsilon-Biased Sets

Anupa Sunny
Chennai Mathematical Institute.


This talk is based on a recent paper by Amnon Ta-Shma on the construction of epsilon biased sets which have a support size close to the Gilbert-Varshamov bound, a notion from coding theory. We will look at the Rozenman-Wigderson construction of the epsilon-biased set in which the bias of a set is amplified by taking a walk over an expander. We will then look at Ta-Shma's construction which is based on a modified version of the zigzag product, namely the s-wide replacement product. If time permits, we will go into the details of the bias analysis of the set constructed.