Ein Vergleich von Extraktoren in Bezug auf Kompromisse zwischen Zeit, Zufall und Raum?

21

Gibt es eine gute Umfrage, die verschiedene Extraktoren, Konzentratoren und Superkonzentratoren vergleicht und die besten Methoden in Bezug auf den Kompromiss zwischen Zufälligkeit, Zeit und Raum aufzeigt?

reference-request randomness derandomization Suresh Venkat
quelle
1
Hallo Suresh, ich denke nicht, dass Extraktoren und (Super-) Konzentratoren vergleichbar sind. Vielleicht habe ich die Frage falsch verstanden und Sie wollten die Konstruktionsalgorithmen vergleichen? Parameter für (Super) -Konzentratoren, die uns wichtig sind, sind ihre Tiefen und Größen, nicht "Zufälligkeit, Zeit und Raum". [Radhakrishnan und Ta-shmas Artikel] [1] enthält eine Tabelle mit allen engen Ergebnissen (einschließlich Referenzen) für Superkonzentratoren. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo,
Danke für die Klarstellung. Ich habe die Unterschiede zwischen ihnen nie ganz verstanden.
Suresh Venkat

Antworten:

12

Die Standardreferenz ist Ronen Shaltiels Umfrage . Dies ist älter als die wichtigen Ergebnisse von [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] usw. Ich glaube, Anup Raos Doktorarbeit . Diese These ist eine gute Referenz aus jüngster Zeit, die diese Entwicklungen beschreibt.

Arnab
quelle