Last update: RNDr. Ondřej Pangrác, Ph.D. (06.05.2019)
Intensive course on one of selected fundamental topics in discrete mathematics and computer science, part of
AlgoMaNet lecture series.
Last update: RNDr. Ondřej Pangrác, Ph.D. (06.05.2019)
Intenzivní kurz na některé z fundamentálních témat z diskrétní matematiky a teoretické informatiky v rámci
programu AlgoMaNet.
Syllabus -
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (21.12.2019)
The series of lectures will provide a tutorial on fine-grained complexity. Fine-grained complexity which emerged over the past decade maps the landscape of problems solvable in polynomial time, and provides insight into their exact asymptotic complexities. By building a formal connection between the complexity of problems like the Longest Common Subsequence and the complexity of solving NP-complete problems such as SAT it provides a plausible explanation why despite lots of effort we did not manage to improve on the trivial quadratic or cubic algorithms for such problems. The course will cover the Strong Exponential Time Hypothesis (SETH) and its variants, problems in P such as Orthogonal Vectors Problem, 3SUM, Longest Common Subsequence and many others, and exhibit a striking relationships between their complexities.
Last update: RNDr. Ondřej Pangrác, Ph.D. (07.05.2019)
Konkrétní téma a syllabus bude oznámen na webových stránkách programu