Une comparaison des extracteurs en termes de compromis entre le temps, le hasard et l'espace?

21

Existe-t-il une bonne enquête qui compare différents extracteurs, concentrateurs et superconcentrateurs et présente les meilleures méthodes en termes de compromis entre le caractère aléatoire, le temps et l'espace?

reference-request randomness derandomization Suresh Venkat
la source
1
Salut Suresh, je ne pense pas que les extracteurs et les (super) concentrateurs soient comparables. J'ai peut-être mal lu la question, et vous vouliez dire comparer les algorithmes de construction? Les paramètres des (super) -concentrateurs qui nous intéressent sont leur profondeur et leur taille, et non "le caractère aléatoire, le temps et l'espace". [L'article de Radhakrishnan et Ta-shma] [1] a un tableau montrant tous les résultats serrés (y compris les références) pour les super-concentrateurs. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
Merci pour la clarification. Je n'ai jamais bien compris les différences entre eux.
Suresh Venkat

Réponses:

12

La référence par défaut est l' enquête de Ronen Shaltiel . C'est antérieure à la résultats importants de [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc. Je crois de Anup Rao Ph.D . thèse est une bonne référence récente qui décrit ces développements.

Arnab
la source