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. See

• Papadimitriou: On the complexity of the parity argument and other inefficient proofs of existence
• Etessami and Yannakakis: On the Complexity of Nash Equilibria and Other Fixed Points
• Deligkas, Fearnley, Hollender, and Melissourgos: Pure-Circuit: Tight Inapproximability for PPAD
• Filos-Ratsikas, Hansen, Høgh, and Hollender: FIXP-Membership via Convex Optimization: Games, Cakes, and Markets
• Filos-Ratsikas, Hansen, Høgh, and Hollender: PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
                                  

Apr 17th: 10-12 Thore Husfeldt: Oh Yes
13-14 Riko Jacob: Fragile Complexity
14-17 Morgan Shirley: Communication Complexity and the Log-Rank Conjecture

May 1st: TBA,

May 8th: Student presentations.
A student presentation could be one of the following:

• short presentation of an item from your own research that relates to the course content or course topic
• short presentation of the solution to one of the exercises from the course
• short recap of one of the proofs or ideas or results from the course

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 circa 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)