SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Seminar on Computational Complexity - NTIN050
Title in English: 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 [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Additional information:
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
Annotation -
Last update: T_KAM (06.05.2001)
Seminar on computational complexity and related combinatorial problems. Recent papers and results of the participants are presented.
Aim of the course - Czech
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 -
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.

Literature - Czech
Last update: T_KAM (22.04.2003)

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

Syllabus -
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.
Charles University | Information system of Charles University |