Paradigms for Unconditional Pseudorandom Generators
A feltétel nélküli pszeudorandom generátorok (PRG-k) átfogó áttekintésében a szerzők intuitív bevezetést nyújtanak az olvasónak a számítás korlátozott modelljeihez tartozó feltétel nélküli PRG-k építésének néhány legfontosabb keretrendszerébe és technikájába. A szerzők a PRG-k tervezésének négy fő paradigmáját tárgyalják: számos PRG-t, amelyek k-bölcs egyenletes generátorokon, kis előfeszítésű generátorokon és ezek egyszerű kombinációin alapulnak, számos PRG-t, amelyek a véletlen bitek „újrahasznosításán” alapulnak a kommunikációs szűk keresztmetszetek kihasználása érdekében, a PRG-k és a számítási keménység közötti kapcsolatokat, valamint a véletlenszerű korlátozásokon alapuló PRG-kereteket.
A szerzők elmagyarázzák, hogyan használhatók ezek a paradigmák olyan PRG-k konstruálására, amelyek feltétel nélkül, bizonyítatlan matematikai feltételezések nélkül működnek. A PRG-konstrukciók olyan összetevőket használnak, mint a véges mező aritmetika, az expandergráfok és a véletlenszerűség-kinyerők.
Az elemzések olyan technikákat használnak, mint a Fourier-analízis, a szendvicses közelítők és az egyszerűsítés a megszorítások alatt lemma. A Paradigms for Unconditional Pseudorandom Generators (A feltétel nélküli álvéletlen generátorok paradigmái) az olvasónak alapozást nyújt egy, az elméleti informatikában és a kriptográfiában széles körben használt fontos témában.