SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Probability and Cryptography - NMMB407
Title: Pravděpodobnost a kryptografie
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:4/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: not taught
Language: Czech, English
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NMMB432
Additional information: http://dostanou moje poznamky na konci semestru
Guarantor: Mgr. Pavel Hubáček, Ph.D.
Class: M Mgr. MMIB
Classification: Mathematics > Algebra, Probability and Statistics
Incompatibility : NMIB051
Interchangeability : NMIB051, NMMB432
Is interchangeable with: NMMB432, NMIB051
Annotation - Czech
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (07.12.2018)
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:
Syllabus - Czech
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (07.12.2018)

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html