Uruchamianie algorytmu BPP z ciągiem pół losowym, pół-przeciwnym

Rozważ następujący model: ciąg n-bitowy r = r ₁ ... r _n jest wybierany równomiernie losowo. Następnie każdy indeks i∈ {1, ..., n} jest umieszczany w zbiorze A z niezależnym prawdopodobieństwem 1/2. Wreszcie, przeciwnik może, dla każdego i∈A osobno, odwrócić r _i, jeśli chce.

Moje pytanie brzmi: czy wynikowy ciąg (nazwij go r ') może być wykorzystywany przez algorytm RP lub BPP jako jedyne źródło losowości? Załóżmy, że przeciwnik zna z góry cały algorytm BPP, ciąg ri zbiór A oraz że ma nieograniczony czas obliczeń. Załóżmy również (oczywiście), że algorytm BPP nie zna ani decyzji przeciwnika, ani A.

Wiem, że jest długa praca nad tym właśnie pytaniem, od pracy Umesh Vazirani nad źródłami pół losowymi (inny, ale powiązany model), po nowsze prace nad ekstraktorami, fuzjami i kondensatorami. Moje pytanie brzmi więc po prostu, czy któraś z tych prac przynosi pożądane rezultaty! Literatura na temat słabych źródeł losowych jest tak duża, z tak wieloma subtelnie różnymi modelami, że ktoś, kto zna tę literaturę, może prawdopodobnie zaoszczędzić mi dużo czasu. Z góry dziękuję!

Potrzebny jest „ekstraktor z nasionami” o następujących parametrach: ziarno o długości , surowa losowość n / 2 i długość wyjściowa n Ω ( 1 ) . Te są znane. Chociaż nie jestem na bieżąco z najnowszymi ankietami, uważam, że sekcja 3 ankiety Ronen jest wystarczająca.$O(\log n)$$n/2$$n^{\Omega(1)}$

Jedyne, co musisz pokazać, to to, że twoje źródło ma wystarczającą „min-entropię”, tj. Żaden ciąg n-bitowy nie ma prawdopodobieństwa większego niż , co moim zdaniem jest jasne w twoim otoczeniu.$2^{-n/2}$

Czy przeciwnik może zobaczyć cały ciąg r przed podjęciem decyzji, jak ustawić bity w A? Jeśli odpowiedź brzmi „nie”, to jest to źródło poprawiające bity, które w rzeczywistości jest deterministycznie możliwe do wyodrębnienia. Oznacza to, że nie jest wymagane naprawdę losowe ziarno. Zobacz na przykład Kamp i Zuckerman, aby zapoznać się z konstrukcjami ekstraktorów dla źródeł mocowania bitów.

Jeśli przeciwnikowi pozwolono zobaczyć resztę ciągu, nadal sądzę, że można go deterministycznie wydobyć, ale modele są nieco inne i nie wiem od początku, jak się odnoszą. Ponieważ zestaw A jest losowy, w rzeczywistości jest nawet bardziej przyjazny niż źródło poprawiające bity, gdzie zestaw A może być dowolny.

Noam ma oczywiście rację. Historycznie, pierwsza symulacja BPP ze źródłem dowolnej stałej szybkości entropii została podana w mojej pracy „Symulowanie BPP przy użyciu ogólnego słabego źródła losowego”. Teraz są prostsze sposoby na osiągnięcie tego i jeszcze silniejsze wyniki.

Deterministyczna ekstrakcja więcej niż stałej liczby bitów jest niemożliwa w twoim modelu. (Możesz uzyskać słabą deterministyczną ekstrakcję 1 bitu, po prostu wyprowadzając pierwszy bit.) Kamp i ja pokazaliśmy, że niemożliwe jest wyodrębnienie więcej niż stałej liczby bitów w ogólnym, nieświadomym źródle utrwalającym bity o stałej szybkości entropii, ale ponieważ zestaw A jest losowy, wyniki te nie mają zastosowania, jak podano. Jednak nasz dowód działał, wybierając losowo A o stałym rozmiarze t, więc wybierając t = .6n, powiedzmy, wynik dla równomiernie losowego A nastąpi.