Informally speaking, extractors are functions that given weak random sources “extract” out the randomness in the source and return almost pure random bits. See the survey titled Recent developments in extractors by Shaltiel for a more thorough definition as well as a listing of some of the numerous applications of extractors.
The paper titled Extractors and Pseudorandom Generators (STOC99) by Trevisan is a milestone paper in the history of development of extractors. This was the first time that list decoding was used in the construction of extractors (though it is not considered to be a milestone paper for this connection :-)). See Shaltiel’s survey for more details on subsequent developments. The current best parameters for extractor construction is achieved by the very recent paper titled Unbalanced expander and randomness extractors from Parvaresh-Vardy codes (CCC07) by Guruswami, Umans and Vadhan, which make crucial use of some recent developments in the constructions of good list decodable codes (we will study these latter developments in the course).
There also has been traffic the other way around. In particular, extractors have been used to construct codes. One of the recent work in this vein is the paper by Guruswami titled Better Extractors for Better Codes? (STOC04).
Posted in projects
