Náhodnost a výpočty

Sylabus

Pravděpodobnostní metoda:

- local Lovazs lemma

- linearity of expectation

- the second moment method

Náhodné procházky:

- zajímavé aplikace pro Markovovy řetězce

- undirected S-T connectivity v logspace

Aplikace náhodnosti v interaktivních důkazových systémech:

- polynomial identity testing

- IP=PSPACE

- probabilistically checkable proofs

Pseudonáhodnost a derandomizace:

- pravděpodobnostní třídy jako BPP

- pseudonáhodné generátory

- Nisan-Wigderson PRG a derandomizace

Anotace

Pravděpodobnostní metoda. Náhodné procházky.

Aplikace náhodnosti v interaktivních důkazových systémech: polynomial identity testing. Pseudonáhodnost a derandomizace: