Selected Topics in Computational Complexity II - NTIX086

• Title: Vybrané kapitoly z výpočetní složitosti II
• Guaranteed by: Student Affairs Department (32-STUD)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Is provided by: NTIN086
• 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
• Pre-requisite : {NXXX036, NXXX037}
• Incompatibility : NTIN086
• Interchangeability : NTIN086

Annotation

English

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.

Czech

Last update: T_KTI (12.05.2006)

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Každý semestr bude věnován jinému tématu. Mezi plánovaná témata patří oblast náhodnosti a pseudonáhodných generátorů, komunikační složitost a interaktivní protokoly, samoopravné kódy a jejich užití ve složitosti, dolní odhady, expandery a jejich použití a další. 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.

Aim of the course

Last update: T_KTI (23.05.2008)

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

Syllabus

English

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.

Czech

Last update: T_KTI (12.05.2006)

• Náhodnost a pseudonáhodné generátory.

• Komunikační složitost a interaktivní protokoly.

• Samoopravné kódy.

• Dolní odhady.

• Expandery a jejich použití.