Introduction to the complexity of CSPs

Lecturers: Peter Zeman and Maximilian Hadek

Schedule: Wednesday 9:00–10:30 in K334KA

What we did in class

• 01.10.2025: We introduced the notion of relational structure. For a relational structure \(\mathbb{A}\), we defined the constraint satisfaction problem \(\text{CSP}(\mathbb{A})\) and found polynomial-time algorithms for some special cases. [Sheet 1, Problem 1]
• 08.10.2025: Plan: finish the first exercise sheet. Equivalent definition of \(\text{CSP}(\mathbb{A})\) using homomorphisms of relational structures.

References (they contain spoilers)

• Survey by Barto, Krokhin, Willard.
• Lecture notes by Bodirsky.
• YouTube playlist by Bodirsky.
• Tutorial by Barto.
• Lecture notes by Kazda, Maróti.
• A rendezvous of logic, complexity, and algebra by Chen.