21

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 ?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 1
    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 has a table showing all the tight results (including references) for super-concentrators.

     – Hung Q. Ngo Aug 17 '10 at 02:21
  • Thanks for the clarification. I've never quite understood the differences between them. – Suresh Venkat Aug 17 '10 at 03:09

1 Answers1

12

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.

arnab
  • 7,000
  • 1
  • 38
  • 55