Seminar on Computational Complexity - NTIN050

• Title: Seminář z výpočetní složitosti
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2009
• Semester: both
• E-Credits: 3
• Hours per week, examination: 0/2, C [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Additional information: http://www.math.cas.cz/~koucky/complexity/
• Note: you can enroll for the course repeatedly; you can enroll for the course in winter and in summer semester
• Guarantor: prof. RNDr. Pavel Pudlák, DrSc.; prof. Mgr. Michal Koucký, Ph.D.
• Class: Informatika Mgr. - volitelný
• Classification: Informatics > Theoretical Computer Science
• Is incompatible with: NTIN053
• Is interchangeable with: NTIN053

Annotation

English

Last update: T_KAM (06.05.2001)

Seminar on computational complexity and related combinatorial problems. Recent papers and results of the participants are presented.

Czech

Last update: T_KAM (14.04.2002)

Seminář zaměřený na výpočetní složitost a související kombinatorické problémy. Referují se zejména aktuální články a výsledky účastníků a hostů semináře. Je vhodný pro studenty, kteří se chtějí specializovat v této oblasti a pro doktorandy. Některé referáty budou v angličtině. Aktuální informace na adrese http://www.math.cas.cz/~sgall/complexity/.

Aim of the course

Last update: SGALL/MFF.CUNI.CZ (07.04.2008)

Získat přehled o aktuální literatuře a zajímavých výsledcích v teorii složitosti.

Course completion requirements

English

Last update: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)

Credit for the seminar is obtained for regular active participation at the seminar which includes at least one presentation at the seminar during the semester.

There is no make up for getting the credit.

Czech

Last update: prof. Mgr. Michal Koucký, Ph.D. (09.10.2017)

Zápočet se uděluje za aktivní pravidelnou účast na semináři a alespoň jednu prezentaci na semináři během semestru.

Zápočet nelze opakovat.

Literature

Last update: T_KAM (22.04.2003)

Většinou aktuální články v angličtině.

Syllabus

English

Last update: SGALL/MFF.CUNI.CZ (07.04.2008)

Recent topics include:

• Sublinear algorithms.

• Error-correcting codes and their applications in complexity.

• Low degree polynomials and use of algebraic methods in complexity.

• Boolean complexity, lower bounds for explicit functions, formulas, branching programs.

• Lower bounds for propositional proof systems.

• Communication complexity.

• Combinatorial problems related to complexity. Expanders. Extremal combinatorics of set systems.

Czech

Last update: SGALL/MFF.CUNI.CZ (07.04.2008)

Výběr témat se přizpůsobuje zájmům účastníků. V poslední době jsme se zabývali těmito oblastmi:

• Sublineární algoritmy

• Kódy a jejich použití v teorii složitosti.

• Reprezentace pomocí polynomů a použití algebraických metod ve složitosti.

• Booleovská složitost, dolní odhady výpočetní složitosti explicitních funkcí, formule, branching programy.

• Dolní odhady pro výrokové kalkuly.

• Komunikační složitost.

• Kombinatorické problémy související se složitostí. Expandery. Extremální kombinatorika množinových systémů.