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...
Czy możliwe jest zbudowanie wyraźnej macierzy z , tak aby każda podmacierz zawiera mniej niż ?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Lub prawdopodobnie możliwe jest zbudowanie jawnego zestawu uderzeń dla takiej...
Mówi się, że rozkład ϵ -fooluje funkcję f if | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Mówi się, że oszuka klasę funkcji, jeśli oszuka każdą funkcję w tej klasie. Wiadomym jest, że ε -biased obowiązuje oszukać klasę parytetów nad podzbiorów. (patrz...
O ile mi wiadomo, większość implementacji generowania liczb pseudolosowych w praktyce wykorzystuje metody, takie jak rejestry sprzężenia zwrotnego z przesunięciem liniowym (LSFR) lub te algorytmy „Mersenne Twister”. Chociaż zdają wiele (heurystycznych) testów statystycznych, nie ma teoretycznych...
Czytam klasyczny utwór „Twardość kontra losowość” Nisana i Wigdersona. Niech B = { 0 , 1 }b={0,1}B=\{0,1\} , a ustalenie funkcją l : N → Nl:N.→N.l\colon \mathbb{N} \to \mathbb{N} . Określają one rodzinę funkcji G = { Gn: Bl ( n )→ B.n}sol={soln:bl(n)→bn}G = \{G_n : B^{l(n)} \to B^n\} być...
Interesuje mnie generowanie liczb pseudolosowych do kryptografii. Oprócz rozdziału 5 Menezes / Oorschot / Vanstone ; Rozdział 8 Stinson ; i rozdział 3 Goldreich , gdzie jeszcze mogę znaleźć więcej? Interesują mnie ogólne zasady projektowania PRNG (pożądane właściwości, testy...
Niech będzie stałą. Jak możemy w sposób wiarygodny skonstruować pseudolosowy generator, który oszuka -state skończone automaty?dreddredd Tutaj automat skończony -state ma węzły, węzeł początkowy, zestaw węzłów reprezentujących stany akceptacji i dwie skierowane krawędzie oznaczone 0, 1 wychodzące...
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ (...
Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do...
Odwrotne włączenie jest oczywiste, podobnie jak fakt, że każdy samonredukowalny język NP w BPP jest również w RP. Czy znane jest to również w przypadku języków NP
Czy były jakieś próby wykazania, że losowość Kołmogorowa byłaby wystarczająca dla RP ? Czy prawdopodobieństwo użyte w stwierdzeniu „Jeśli prawidłowa odpowiedź brzmi TAK, to wówczas (probabilistyczna maszyna Turinga) zwraca TAK z prawdopodobieństwem ...” zawsze byłoby dobrze zdefiniowane w takim...