Paradigms for Unconditional Pseudorandom Generators
W tym kompleksowym przeglądzie bezwarunkowych generatorów pseudolosowych (PRG) autorzy przedstawiają czytelnikowi intuicyjne wprowadzenie do niektórych z najważniejszych ram i technik konstruowania bezwarunkowych PRG dla ograniczonych modeli obliczeniowych. Autorzy omawiają cztery główne paradygmaty projektowania PRG: kilka PRG opartych na generatorach k-wise uniform, generatorach small-bias i ich prostych kombinacjach, kilka PRG opartych na „recyklingu” losowych bitów w celu wykorzystania wąskich gardeł komunikacyjnych, powiązania między PRG a twardością obliczeniową oraz ramy PRG oparte na losowych ograniczeniach.
Autorzy wyjaśniają, jak wykorzystać te paradygmaty do skonstruowania PRG, które działają bezwarunkowo, bez niesprawdzonych założeń matematycznych. Konstrukcje PRG wykorzystują składniki takie jak arytmetyka pól skończonych, grafy ekspanderów i ekstraktory losowości.
Analizy wykorzystują techniki takie jak analiza Fouriera, aproksymatory kanapkowe i lematy upraszczające w ramach ograniczeń. Paradigms for Unconditional Pseudorandom Generators oferuje czytelnikowi podstawy w ważnym temacie szeroko stosowanym w informatyce teoretycznej i kryptografii.