Vybrané kapitoly z výpočetní složitosti II

Michal Koucký
<koucky@math.cas.cz>

 

LS 2009/2010

 

TIN086 - 2/1 Z, Zk

Čas konání: Čt. 15:40.
Místo konání: S10, Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován interaktivním protokolům a pravděpodobnostním důkazovým systémům (IP, AM, MIP, PCP). Probereme též související témata samoopravných programů, zero-knowledge důkazů a težkosti aproximací.

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky. Přednášku je možné si zapsat opakovaně.

Plán přednášky

Literatura:

Domání úkoly

  1. Do 22.4. 2010.
  2. Do 13.5. 2010.
  3. Do zkoušky.