Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?

  • 1
    $\begingroup$ Hi Suresh, I don't think extractors and (super)-concentrators are comparable. Perhaps I misread the question, and you meant comparing the construction algorithms? Parameters for (super)-concentrators that we care about are their depths and sizes, not "randomness, time, and space". [Radhakrishnan and Ta-shma's paper][1] has a table showing all the tight results (including references) for super-concentrators. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$ Commented Aug 17, 2010 at 2:21
  • $\begingroup$ Thanks for the clarification. I've never quite understood the differences between them. $\endgroup$ Commented Aug 17, 2010 at 3:09

1 Answer 1


The default reference is Ronen Shaltiel's survey. This predates the important results of [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc. I believe Anup Rao's Ph.D. thesis is a good recent reference that describes these developments.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.