Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Selected Topics in Computational Complexity I - NTIN085

Title:	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 2023
Semester:	winter
E-Credits:	4
Hours per week, examination:	winter s.:2/1, C+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
Note:	you can enroll for the course repeatedly

Guarantor:	prof. Mgr. Michal Koucký, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika
Classification:	Informatics > Theoretical Computer Science
Is incompatible with:	NTIX085
Is interchangeable with:	NTIX085

Opinion survey results Examination dates Schedule Noticeboard

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: prof. Mgr. Michal Koucký, Ph.D. (01.10.2021)

Randomness and pseudorandom generators.

Communication complexity and interactive protocols.

Error-correcting codes and their applications in complexity.

Lower bounds.

Expanders and their applications.

For details for 2021/22 see: https://users.math.cas.cz/~talebanfard/mtc.html