Od ekstraktorów do generatorów pseudolosowych?

Luca Trevisan pokazał, ile konstrukcji generatorów pseudolosowych można uznać za konstrukcje ekstraktorów:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Czy istnieje sensowna rozmowa? Tj. Czy „naturalne” konstrukcje ekstraktorów można traktować jako konstrukcje pseudolosowych generatorów (PRG)?

Konstrukcje ekstraktorów wydają się odpowiadać rozkładom na PRG (tak, że żadnemu wyróżniającemu nie uda się rozróżnić dla prawie wszystkich z nich). Czy są na to znane zastosowania?

To piękne pytanie badawcze z kilkoma aspektami, i istnieją różne sposoby sformalizowania pytania w zależności od tego, czy przez ekstraktor masz na myśli ekstraktor zarodkowy czy ekstraktor beznasienny i czy przez PRG masz na myśli PRG dla obwodów logicznych czy bardziej wyspecjalizowaną rodzinę (np. , przestrzenie stronnicze epsilon). Oto kilka nieformalnych myśli z góry mojej głowy (ale nie pełna odpowiedź):

• W przypadku wyodrębnionych ekstraktorów w porównaniu z programami typu black-box (jak w Nisan-Wigderson) wydaje się, że program typu black-box jest silniejszym obiektem niż ekstraktor. Jeśli spojrzysz na ekstraktor Trevisana, jest to nie tylko ekstraktor obliczalny w czasie wielomianowym, ale ma ważną dodatkową właściwość. Mianowicie, analiza zawiera lokalny i wydajny element obliczeniowy (a mianowicie lokalny algorytm dekodowania listy). Ta dodatkowa funkcja nie jest tak ważna dla ekstraktora (jako obiektu kombinatorycznego, nawet jeśli wymagamy, aby ekstraktor był obliczalny w czasie wielomianowym), ale ma kluczowe znaczenie dla PRG (tak, aby wyróżnik można efektywnie przekształcić w algorytm do obliczania trudna funkcja). W rzeczywistości można to sformalizować, a Ta-Shma i Zuckerman sformalizowali już definicję „czarnego skrzynki PRG” w artykule „Kody ekstraktorów”. Pokazują, że do budowy ekstraktorów można wykorzystać czarne skrzynki PRG. Z drugiej strony, myślę, że można pokazać, że każdy ekstraktor, który spełnia powyższą właściwość, odpowiada czarnemu polu PRG (w języku ekstraktora oznaczałoby to, że wynikowy kod ekstraktora musi mieć wydajny dekoder listy decyzji miękkich). Możesz również znaleźć artykuł Vadhana „The Unified Theory of Pseudorandomness” istotny dla tej dyskusji.

• W świecie ekstraktorów bezpestkowych Trevisan i Vadhan pokazują, że twarde funkcje dla konkretnej rodziny obwodów skutkują ekstraktorami dla tej rodziny (artykuł „Ekstraktory dla źródeł Samplable”). Na przykład funkcja, która jest naprawdę bardzo trudna dla AC0, może wyodrębnić ze źródeł próbkowanych przez obwody AC0 (jeśli minimalna entropia źródła jest wystarczająco duża). Twarde funkcje naturalnie odnoszą się do PRG (jak zaobserwował Nisan-Wigderson). Więc tutaj znów otrzymujemy nieco inną grę między PRG i ekstraktorami bezpestkowymi. Nie jest jednak jasne, w jaki sposób można użyć ekstraktora do źródeł próbkowania (być może spełniających pewne dodatkowe właściwości), aby uzyskać PRG (następny punktor daje częściową odpowiedź na to pytanie). Ten kierunek może być mniej interesujący niż powyższa dyskusja dla ekstraktorów z nasionami, ponieważ do tej pory nie „

• $S$$\{0,1\}^n$$n$$0$$2^m$$m$$S$$F$$|S \cap F|/|S|$$|F|/2^n$$F$$S$$|S \cap F|/|S|$$1/2$$\{0,1\}^n$$n-1$$1$$S$$0$$n-1$

Salil Vadhan napisał do mnie, że odpowiedź na moje pytanie jest znana, a PRG są równoważne ekstraktorom.

Cytując go:

„Patrz propozycja 21 i dyskusja po niej w mojej ankiecie http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (istnieje literówka -„ wzmacniacz twardości czarnej skrzynki ”powinien być„ czarny ” -box konstrukcja PRG ”)

Mówi, że ekstraktory są równoważne z czarnymi konstrukcjami PRG, w których zależy tylko na ilości porady, a nie na czasie pracy. Pytanie o ograniczony czas działania sprowadza się do zapytania o ekstraktory z „lokalnym dekodowaniem listy”.

Jest miły artykuł Chrisa Umansa na temat analogii tego pytania dla dyspergatorów: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf

Pokazuje, że dyspergatory, które mają procedurę rekonstrukcji w czasie wielomianowym, ale niekoniecznie lokalną właściwość dekodowania, implikują istnienie uderzania w generatory zestawów.

Oto inny sposób, aby to zobaczyć: Ekstraktory mogą być postrzegane jako kody do odtworzenia z listy (co jest silniejszym wariantem kodów do dekodowania z listy), a programy PRG w czarnej skrzynce mogą być przeglądane z kodów lokalnych do odzyskania z listy. Dyspergatory mogą być postrzegane jako kody do odzyskania z listy dla błędu zerowego. Chris pokazuje, że kod do odtworzenia listy dla błędu zerowego, który ma procedurę odzyskiwania listy w czasie wielomianowym, sugeruje istnienie kodu do odtworzenia listy z lokalną procedurą odzyskiwania listy.