Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi:
[Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego . Zgodnie z naszą najlepszą wiedzą, podejście to jest nowością w tym dokumencie.
Rzuciłem okiem na wpis Wikipedii dotyczący lematu Borela – Cantellego i prawie zrozumiałem ten pomysł. Jednak nadal nie mogłem zrozumieć, w jaki sposób odnosi się to do derandomizacji. Ponadto nie rozumiem znaczenia „asymptotycznego” i „jednolitego” we wspomnianym akapicie.
PS: Googling dla Borela-Cantellego i derandomizacja przyniosą kilka interesujących rezultatów, ale nie mam wystarczającej wiedzy, by je dobrze zrozumieć.
Odpowiedzi:
Nie sądzę, że mają na myśli derandomizację w tradycyjnym sensie. Spróbuj spojrzeć na zastosowanie lematu BC w tym artykule na przykład tego, o czym mówią: http://www.cs.bu.edu/~reyzin/hash.html .
Mówią „asymptotycznie”, ponieważ większość separacji BB dotyczy pojęć takich jak funkcje jednokierunkowe, które są definiowane asymptotycznie. Ich wynikiem jest natomiast „konkretna” granica, która dotyczy wszystkich wartości parametrów bezpieczeństwa, a nie tylko wystarczająco dużych wartości.
źródło