<p>The default reference is Ronen Shaltiel's <a href="http://cs.haifa.ac.il/~ronen/online_papers/survey.ps" rel="noreferrer">survey</a>.  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 <a href="http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf" rel="noreferrer">Ph.D. thesis</a> is a good recent reference that describes these developments.</p>

CC BY-SA 2.5
2010-08-16T21:37:08.057Z
2010-08-16T21:37:08.057Z
arnab
<p>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 ? </p>

CC BY-SA 2.5
2010-08-17T02:21:53.647Z
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]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
CC BY-SA 2.5
2010-08-17T03:09:14.623Z
Thanks for the clarification. I've never quite understood the differences between them.
Suresh Venkat
<reference-request><randomness><derandomization>
A comparison of extractors in terms of tradeoffs between time, randomness and space ?
Suresh Venkat
# A comparison of extractors in terms of tradeoffs between time, randomness and space ?

(Asked by: username_0 on 2010-08-16)

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 ?

**Tags:** reference-request, randomness, derandomization
> **Comments:**
> **username_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][1] has a table showing all the tight results (including references) for super-concentrators.    [1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637  
> **username_0**: Thanks for the clarification. I've never quite understood the differences between them.  

---

## 1 answers

### Answer by username_2 on 2010-08-16. Score: 12 | Accepted answer

The default reference is Ronen Shaltiel's [survey](http://cs.haifa.ac.il/~ronen/online_papers/survey.ps). 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](http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf) is a good recent reference that describes these developments.


---

