Sylabus a literatura k prednasce

"Slozitost pro kryptografii", Jan Krajicek

Kod predmetu: NMIB002
Zkouska je ustni (otazky).
Alternativa pro studenty, kteri prednasku uspesne absolvovali v ramci bakalarskeho studia a maji ji zapsanou podruhe v ramci magisterskeho studia.

Sylabus:

  • Bijekce mezi slovy nad konecnou abecedou a prirozenymi cisly. Jazyky a rozhodovaci problemy. Turingovy stroje (TM). Varianty TM (vice pasek, atd.).

  • Rekursivni funkce (RF) a castecne rek. fce (PRF). Rekursivni mnoziny (R=Delta_1) a rek. vycislitelne mnoziny (RE = Sigma_1). coRE (= Pi_1) mnoziny.

  • Vety: R je prunik RE a coRE. Mnozina je RE prave kdyz je oborem hodnot PRF a tez prave kdyz je projekci rekursivni relace. Souvislost RE mnozin a NTM (nedeterministicke TM).

  • Kodovani TM slovy. Universalni TM. Halting problem (HALT) a 10.Hilbertuv problem. HALT neni rekursivni.

  • Casova slozitost TM a NTM. Polynomialni cas (p-cas), trida P. Trida NP (ekvivalence definic pres NTM a jako p-omezene projekce p-relaci).

  • Prostorova slozitost, tridy L, NL a PSPACE. Obecne vztahy mezi casovou a prostorovou slozitosti: TIME(f) je cast NTIME(f) je cast SPACE(f) je cast TIME(2^{O(f)}).

  • s-t souvislost v orientovanych grafech (algoritmus s log^2(n) prostorovou slozitosti). Savitchova veta: NSPACE(f) je cast SPACE(O(f^2)). Immerman - Szelepscenyi veta: NSPACE(f) = coNSPACE(f) (bez dk.).

  • Hierrarchie trid slozitosti: SPACE(f) je vlastni cast SPACE(g) (je-li f = o(g)),
    TIME(f) je vlastni cast TIME(g) (je-li f log(f) = o(g)) (bez dk.). Tridy E a EXP. NP je cast EXP.

  • Vyrokova logika, booleovske obvody.

  • p-preveditelnost. NP-uplne jazyky. Cook-Levinova veta. SAT, CIRCSAT, 3SAT, 3-obarvitelnost.
    Clanky Cook'71 a Karp'72.

  • P/poly: neuniformni p-cas. Charakterizace vyuzivajici pomocna slova (advice) a booleovske obvody, a jejich ekvivalence. Pozn. o spodnich odhadech pro obvody a souvislosti s P/NP problemem.

  • Pravdepodobnostni algoritmy. Priklady: PIT (polynomial identity testing) a nahodne prochazky po grafech (s-t souvislost; toto bez dk.).

  • Tridy BPP, RP, ZPP. BPP je cast EXP. Amplifikace pravdepodobnosti u RP.
    Pozn. o hypoteze P = BPP (Impagliazzo-Wigdersonova veta - bez dk.).

  • Konecne pravdepodobnostni prostory, jevy, nahodne veliciny. Ocekavana (stredni) hodnota E(X). Linearnost E(X). Pr.: pocet hlav v n hodech minci.

  • Podminena pravdepodobnost, nezavisle jevy a nahodne veliciny, odchylka. Po dvou nezavisle veliciny a linearnost Var(X). Markovova nerovnost, Cebysevova nerovnost (obe s dk.) a Chernoffova (bez dk.).

  • Amplifikace pravdepodobnosti u BPP. BPP je v P/poly.

  • Distribuce a jejich konstruovatelnost. Zanedbatelne a vyznamne funkce. Vypocetne nerozlisitelne distribuce, zakladni vlastnosti. Poly-mnoho nezavislych kopii.

  • Pseudonahodne distribuce. Pseudonahodne generatory (PRNG) a souvislost s P vs. NP problemem.

  • Vlastnosti PRNG a dusledky jejich existence: polynomialni prodlouzeni, derandomizace BPP do sub-exp.casu a pseudonahodne funkce (bez dk.).

  • Jednosmerne funkce (OWF). Slabe OWF a ekvivalence s puvodni definici (bez dk.). PRNG s dostatecnym prodlouzenim je OWF. Pr.: rozklad na prvocisla, diskretni logaritmus, RSA, Rabinova funkce, subset-sum generator.

  • Veta: Existence OWF implikuje existenci PRNG (bez dk.). Dukaz slabsi verse: Existence OWP (permutace) implikuje existenci PRNG. Tezky bit.

  • Goldreich-Levinuv algoritmus a veta (s dk.).

  • Charakterizace PRNG pomoci nepredpoveditelnosti bitu (bez dk.).

  • Interaktivni dukazove systemy. Trida IP, a pozorovani: NP a coRP jsou casti IP. Shamirova veta: IP=PSPACE (bez dukazu). Dukaz specialniho pripadu: coNP je cast IP.

  • PCP dukazovy system. PCP veta (bez dukazu). Alternativni formulace: amplifikace minimalniho poctu nesplnenych klausuli v 3CNF formulich. Dukaz ekvivalence obou formulaci. Idea aplikace: ne-aproximovatelnost optimalizacnich NP-uplnych uloh, dk neaproximovatelnosti 3SAT.

  • Zero-knowledge (dukazove systemy s nulovou znalosti). Varianty: perfektni (PZK), statisticka (SZK) a vypocetni CZK). PZK protokoly pro grafovy izomorfismus a neizomorfismus. CZK protokol pro vsechny NP mnoziny (za predpokladu existence OWF): idea konstrukce CZK protokolu pro 3COLOR.

    Temata, z nichz ktera jsou probirana, je-li dost casu (ale nejsou zkousena):

  • Spodni odhady na velikost booleovskych obvodu: monotoni obvody pro kliku (jen formulace), obvody konstantni hloubky pro paritu (dukaz aproximacni metodou Razborov-Smolensky).
    (Boppana-Sipser'89)

  • Komunikacni slozitost a Karchmer-Wigdersonova veta (dukaz). Priklad: parita.
    (Razborov'11)

  • "Natural proofs" Razborova a Rudiche a veta o jejich neexistenci (s dk.).
    (Razborov-Rudich'99)

  • Efektivni interpolace pro rezoluci, tezko oddelitelne disjunktni NP pary.
    (Krajicek'97)

  • Pet svetu R.Impagliazza.
    (Impagliazzo'95)

    Literatura na webu:

  • skripta Stepana Holuba (cesky, obsahuji jen cast probirane latky)


    Vynikajici je sbornik prednasek:

  • Steven Rudich, Avi Wigderson eds.: Computational Complexity Theory, AMS | PCMI, 2004, 389 pp..

    Neni sice online, ale vetsi cast je na Google books a nektere prednasky relevatni k nasemu sylabu jsou jednotlive online tez:

  • Sanjeev Arora, Exploring Complexity Through Reductions, (obsahuje PCP a souvislost s neaproximovatelnosti)

  • Oded Goldreich, Pseudorandomness - part I.
    (casti 1 a 2 obsahuji material o vypoctni nerozlisitelnosti distribuci, pseudonahodnych generatorech, vetu o prodlouzeni, jednosmerne funcke a jejich tezky bit, konstrukce PRNG z OWP)

  • Luca Trevisan, Pseudorandomness - part II.
    (obsah neprobirame, ale nekoho to muze zajimat)

  • Salil Vadhan, Probabilistic proof systems - part I.
    (obsahuje Interactive proofs a Zero-Knowledge Proofs)

  • Madhu Sudan, Probabilistic proof systems - part II
    (obsahuje PCP)


    Lecture notes z ruznych kursu a rukopisy knih (finalni verse nejsou typicky online):

  • Boaz Barak's courses
    (seznam obsahuje zakladni prednasky slozitosti a kryptografie)

  • a draft of Sanjeev Arora a Boaz Barak's book "Complexity Theory: A Modern Approach".
    (obsahuje vse probirane a velmi mnoho neprobiraneho, bohuzel take hodne tiskovych i vecnych chyb a nepresnosti, t.j. pouzivejte opatrne)

  • Jonathan Katz's course
    (obsahuje mnoho probiraneho - P, NP, NP-uplnost, pravdepodobnosti tridy, IP, zero-knowledge, PCP, ..., ale typicky jen velmi strucne poznamky psane studenty a jinak odkazuje k castem v Arora-Barak)

  • Oded Goldreich,
    "Foundations of Cryptography" a "Computational Complexity: A Conceptual perspective".
    (na strankach jsou k dosazeni rukopisy dvou jiz vyslych knih - obsahuji skoro vse probirane a mnoho dalsiho materialu)


    Toto jsou dve prednasky z kryptografie - z toho neprobirame skoro nic, ale uvadim pro zajimavost (druha prednaska obsahuje i material o OWF a PRNG a o jejich pouziti).

  • Bellare-Rogaway course ("Introduction to Modern Cryptogtaphy")

  • Bellare-Goldwasser course (lecture notes on cryptography)