Selected Topics in Computational Complexity I

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

NTIN085 - 2/1 Z, Zk

Time: Bude umluveno na společné úmluvě KAM-IUUK.
Place: Malá Strana.

This course covers advanced topics in computational complexity. This semester it will focus on edit distance. Edit distance is a measure of string similarity. It has various applications in bioinformatics, text processing, etc. In this course we will focus on various aspects of edit distance: from algorithms and lower bounds to sketching and error-correction. This will showcase various algorithmic and complexity issues.

The course is primarily intended for senior students and phd students. The course assumes basic knowledge of computational complexity, probability, and discrete mathematics. The course can be taken repeatedly.

Tentative plan of lectures

• Dynamic programming, Landau-Vishkin algorithm.
• Fine-grained lower bounds (Backurs-Indyk, Lifshits).
• Planar reachability algorithms (Klein, Das-Kipouridis-Gutenberg-Wulff-Nilsen).
• Seaweed technique, Monge matrices (Tiskin, Russo, Gawrychowski-Gorbachev-Kociumaka).
• Approximation algorithms.
• Sublinear algorithms.
• Error-correcting codes for edit distance.
• Sketching edit distance, embedding of edit distance into Hamming distance and vice-versa.
• Pattern-matching (Porat-Porat).
• Compressed strings, LZ, measures of string complexity.

Literature:

• Various research articles

Homeworks