21.03.14: Twierdzenie Goldreicha-Levina, konstrukcja Goldreicha, Goldwasser i Micali'ego

Wykład zaczęliśmy sformułowaniem twierdzenia (bez dowodu), że nieprzewidywalność kolejnego bitu jest równoważna pseuodolosowości.  Znajduje się ono w Pozdrozdziale 9.3.1 Rozdziału 9 ksiażki

Sanjeev Arora and Boaz Barak Computational Complexity: A Modern Approach.

Następnie pokazaliśmy Twierdzenie Goldreicha-Levina (z dowodem). Całość można znaleźć w Pozdrozdziale 9.3.2 tej samej książki.

Na ćwiczeniach pokazaliśmy konstrukcję funkcji pseudolosowej z generatora pseudolosowego (wraz z dowodem). Można ją znaleźć w Rozdziale 4 tych notatek autorstwa Yevgeniy'a Dodisa.