SubjectsSubjects(version: 850)
Course, academic year 2019/2020
   Login via CAS
Selected Topics in Computational Complexity I - NTIN085
Title in English: Vybrané kapitoly z výpočetní složitosti I
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2019 to 2019
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Note: you can enroll for the course repeatedly
Guarantor: prof. Mgr. Michal Koucký, Ph.D.
Mgr. Martin Koutecký, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: T_KTI (12.05.2006)
This course covers advanced topics in computational complexity. Each semester will be devoted to a different topic. Topics will include among others: randomness and pseudorandom generators, communication complexity and interactive protocols, error-correcting codes and their applications in complexity, lower bounds, expanders and their applications. The course is intended to students from upper classes and to graduate students. Prerequisites: understanding of elementary concepts from computational complexity, probability theory and discrete math.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)

Naučit vybrané kapitoly z výpočetní složitosti

Course completion requirements -
Last update: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)

The credit from tutorials is given based on the number of points obtained from the homework assignments. To get the credit one has to get at least 50% of the total number of points

for the assignments, and one has to solve at least some problem from at least 3/4 of the assignments.

There are no make-up homeworks.

The credit from tutorials has to be obtained before taking an exam.

Requirements to the exam -
Last update: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)

The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.

Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.

Syllabus -
Last update: T_KTI (12.05.2006)
  • Randomness and pseudorandom generators.
  • Communication complexity and interactive protocols.
  • Error-correcting codes and their applications in complexity.
  • Lower bounds.
  • Expanders and their applications.

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