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: