Сравнение экстракторов с точки зрения компромиссов между временем, случайностью и пространством?

21

Существует ли хороший опрос, в котором сравниваются различные экстракторы, концентраторы и суперконцентраторы и излагаются лучшие методы с точки зрения компромисса между случайностью, временем и пространством?

reference-request randomness derandomization Суреш Венкат
источник
1
Привет Суреш, я не думаю, что экстракторы и (супер) -концентраторы сопоставимы. Возможно, я неправильно понял вопрос, а вы имели в виду сравнение алгоритмов построения? Параметры (супер) -концентраторов, которые нас интересуют, это их глубина и размеры, а не «случайность, время и пространство». [В статье Радхакришнана и Та-шмы] [1] есть таблица, показывающая все точные результаты (включая ссылки) для суперконцентраторов. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Хунг Q. Ngo
Благодарю за разъяснение. Я никогда не понимал различия между ними.
Суреш Венкат

Ответы:

12

По умолчанию используется опрос Ронена Шалтиэля . Это предшествует важным результатам [Барак-Импальяццо-Вигдерсон '04], [Барак-Киндлер-Шалтиэль-Судаков-Вигдерсон '05], [Барак-Рао-Шалтиэль-Вигдерсон '06] и т. Д. Я считаю, что доктор философии Ануп Рао , Тезис является хорошей недавней ссылкой, которая описывает эти события.

Арнаб
источник