Pytania otagowane jako pseudorandom-generators

3
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). …
6
Równoległe generatory liczb pseudolosowych
Pytanie to dotyczy przede wszystkim praktycznego problemu z inżynierią oprogramowania, ale z ciekawością dowiedziałbym się, czy teoretycy mogliby uzyskać wgląd w ten problem. Mówiąc prościej, mam symulację Monte Carlo, która korzysta z generatora liczb pseudolosowych i chciałbym go zrównoleglić, aby 1000 komputerów działało równolegle z tą samą symulacją. Dlatego potrzebuję …
2
Jawna zrównoważona macierz
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 właściwości. Łatwo zauważyć, że macierz losowa ma tę właściwość z prawdopodobieństwem wykładniczo bliskim . Również lemat mieszania ekspandera nie …
2
Czy w praktyce wykorzystywane są teoretycznie generatory pseudolosowe?
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 gwarancji, że wyglądają pseudolosowo, powiedzmy, na wszystkie skutecznie obliczalne testy statystyczne. Jednak metody te …
3
Przykłady udanej derandomizacji z BPP na P.
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet w tym przypadku istniała metodologia zakładająca GRH). Więc jakie konkretne dowody na przykładzie …
2
Generator pseudolosowy dla automatów skończonych
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 z każdego węzła. Zmienia stan w naturalny sposób, odczytując dane wejściowe. Biorąc pod …
3
Derandomizacja strumieniowa
Algorytmy strumieniowe wymagają w większości przypadków randomizacji, aby zrobić coś nietrywialnego, a ze względu na ograniczenie małej przestrzeni potrzebują programów PRG, które zajmują mało miejsca. Znam dwie metody, które do tej pory były cytowane w algorytmach strumieniowych: -niezależne PRG-y, takie jak 4-mądra, niezależna rodzina używana przez Alona / Matiasa / …
1
Słynny papier P = BPP Impagliazzo i Wigdersona
Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P = B P PP.=bP.P.\mathsf P=\mathsf{BPP} Szukam …
2
Oszukiwanie
Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?logO ( d)( n )logO(d)⁡(n)\log^{O(d)}(n)A C.0AC0AC^0reddnnn Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy C 0 obwody głębokości D …
2
Czy kryptologowie odradzają rejestrom przesuwnym liniowe sprzężenie zwrotne?
Katz i Lindell wspominają w swojej książce, że LFSR są okropne jako podstawa dla generatorów pseudolosowych i zalecają, aby nie były już używane (cóż, zalecają również, aby ludzie używali szyfrów blokowych zamiast szyfrów strumieniowych). Widzę jednak na przykład, że jeden z szyfrów w portfolio estream ( ziarno , ukierunkowane na …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.