PhD Course at ITU: Advanced Topics in Computational Complexity.

Where: IT University of Copenhagen, Rued Langgaards Vej 7, 2300 Kbh S, Auditorium 4 also known as 4A60, on 4th floor of the main building.

This PhD Course is taught by the Algorithms and Complexity group of ITU and friends.

Dates and content:

Feb 6th: Srikanth Srinivasan and Amik Raj Behera: The PCP theorem (and the proof of a weaker version),
See: this google doc for reading material and more.

Feb 20th:
10-12: Lasse Wulf: The polynomial hierarchy, Σ-2-completeness, complexity of robust optimisation problems
See: Reading material
13-17: Radu Curticapean: Algebra for algorithms, fine-grained complexity,
See: https://algebraicgraphalgorithms.wordpress.com/ and https://arxiv.org/abs/2410.02606

Mar 6th:
10-12: Kilian Risse: Supercritical Tradeoffs for Monotone Circuits (see this arxiv paper),
13-17: Ivor van der Hoog: Universal Optimality. See

• On the Worst-Case Complexity of TimSort,
• Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps,
• Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull [up to and including Section 3], and
• Instance Optimal Geometric Algorithms.

Mar 20th: Kristoffer Arnsfelt Hansen: PPAD and FIXP.

Apr 17th: TBA,

May 1st: TBA,

May 15th: TBA.

We plan to cover topics such as e.g. the following:

• Fine-grained complexity
• Algebraic complexity
• Existential theory of the reals
• Fragile complexity
• Proof complexity
• Parameterised complexity
• Sigma two completeness

We meet every second week, Fridays, starting 10:15, at ITU. (Except for during Easter.)

These times are chosen to comfortably fit the 08:00 train from Odense and the 08:50 train from Lund.

Daily schedule will be something like:

• 10:15 am to noon: Theme 1
• noon to 1:15 pm: Lunch break
• 1:15 pm to 3 pm: Theme 2
• 3 pm: cake break
• Finally: Continued discussions either together or in groups, inspired by today's topics.

Who can sign up:

• Prerequisites: mathematical maturity, knowledge of computational complexity.
• Any PhD student of computer science, mathematics, or closely related topics can join.
• In case of doubt, or in case you are not a PhD student, you must contact the course organisers to enroll. Include a transcript of passed courses and projects in your mail.

How to sign up: Contact the course organisers, Eva Rotenberg (erot@itu.dk) and Ivor van der Hoog (ivva@itu.dk)