Porównanie ekstraktorów pod względem kompromisu między czasem, przypadkowością i przestrzenią?

21

Czy istnieje dobra ankieta, która porównuje różne ekstraktory, koncentratory i superkoncentratory i określa najlepsze metody pod względem kompromisu między losowością, czasem i przestrzenią?

reference-request randomness derandomization Suresh Venkat
źródło
1
Cześć Suresh, nie sądzę, że ekstraktory i (super) koncentratory są porównywalne. Być może źle odczytałem pytanie, a miałeś na myśli porównanie algorytmów konstrukcyjnych? Parametry (super) koncentratorów, na których nam zależy, to ich głębokości i rozmiary, a nie „losowość, czas i przestrzeń”. [Artykuł Radhakrishnana i Ta-shmy] [1] zawiera tabelę pokazującą wszystkie ścisłe wyniki (w tym referencje) dla superkoncentratorów. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
Dziękuję za wyjaśnienie. Nigdy do końca nie rozumiałem różnic między nimi.
Suresh Venkat

Odpowiedzi:

12

Domyślnym odniesieniem jest ankieta Ronena Shaltiela . To poprzedza ważne wyniki [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] itd. Uważam, że doktorat Anup Rao . Teza jest dobrym niedawnym odniesieniem, które opisuje te zmiany.

arnab
źródło