21
$\begingroup$

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 ?

$\endgroup$
  • 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=10.1.1.5.3637 $\endgroup$ – Hung Q. Ngo Aug 17 '10 at 2:21
  • $\begingroup$ Thanks for the clarification. I've never quite understood the differences between them. $\endgroup$ – Suresh Venkat Aug 17 '10 at 3:09
12
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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